Containers and arrays with custom memory allocators

[Per Nordlöw]

On Tuesday, 17 October 2017 at 14:14:19 UTC, Ivan wrote:
> Hi,
>
> I am a C/C++ programmer interested in using D as a replacement 
> for C/C++.
>
> I do care a lot about performance and memory management, so
> I want to use my own (or from std.experimental) memory
> allocators.
>
> Are there any good tutorials or examples about how to use
> custom memory allocators for arrays and existing containers?
>
> Or should I just go ahead and write my own containers that are 
> allocator
> aware?
>
> Thanks.

I'm currently working on a set of containers as part of my very 
general repo

https://github.com/nordlow/phobos-next/tree/master/src

For instance:

- 
https://github.com/nordlow/phobos-next/blob/master/src/basic_array.d
- 
https://github.com/nordlow/phobos-next/blob/master/src/bitarray.d
- 
https://github.com/nordlow/phobos-next/blob/master/src/static_bitarray.d
- 
https://github.com/nordlow/phobos-next/blob/master/src/fixed_array.d
- https://github.com/nordlow/phobos-next/blob/master/src/soa.d
- https://github.com/nordlow/phobos-next/blob/master/src/hashmap.d

and a lightweight polymorphic container at

- 
https://github.com/nordlow/phobos-next/blob/master/src/variant_arrays.d

and a very experimental radix-tree (trie) implementation at

- https://github.com/nordlow/phobos-next/blob/master/src/trie.d

These are all very performant containers, but currently lack 
support for std.experimental.allocator. Instead they use C-style 
allocation (via qualified C-memory management in qcmeman.c). 
Further they use Rust-like semantics via disabling of 
copy-construction; `@disable this(this);`. Instead copying (like 
for EMSI-containers and many others) is forced to be explicit via 
.dup member and when you want to copy or pass by move use, for 
instance,

     import std.algorithm.mutation : move;
     import basic_array : A = BasicArray;

     Ai = A!int;
     auto s = Ai.withLength(10);

     Ai src, dst;
     move(src, dst);

     someFunctionTakingArrayByValue(move(s)); // pass by move

The file hashmap.d provides both a HashSet and HashMap 
implementation in one go using D's 
compile-time-code-branching-mechanism `static if`.

If you want reference semantics (via reference counting) each 
container can be wrapper in a `std.typecons.RefCounted` for 
instance as

     import basic_array : A = BasicArray;
     alias Ai = A!int;
     import std.typecons : RefCounted;
     RefCounted!A x;

used here

https://github.com/nordlow/phobos-next/blob/master/src/basic_array.d#L1288

Further note that my work has focused heavily on making things 
`@safe pure nothrow @nogc` via DIP-25/DIP-1000 when possible 
which is not the case with most other D container libraries I've 
tried. In some cases I might have made a mistake with my @trusted 
taggings. Please correct me if that is the case. Also note that 
DIP-1000 scope analysis doesn't currently kick in correctly in 
templated containers because of a bug in the compiler. The bug 
has been filed at bugzilla and my guess is that it will soon be 
fixed, as making scope analysis more complete is a high priority, 
at least for Walter Bright.

~master currently builds with both dmd (debug mode only) and ldc2 
(both debug and release mode). I'm currently searching for some 
part of trie.d that currently makes dmd segfault when compiled in 
release mode with inlining enabled. I think DMD's inlining is the 
root of the problem so be careful when using trie.d.

My preliminary benchmark at

https://github.com/nordlow/phobos-next/blob/master/benchmarks/source/app.d

compiled with LDC and inlining enabled shows that 
`HashMap!(uint/ulong, uint/ulong)`'s `insert()` and `contains()` 
with FNV64 hash is at least 10 times as fast as D's builtin 
associative arrays on my Intel Haswell laptop.