In C, C++, and D people have allocated memory for a long time in the
following manner:
1. Allocate as many bytes as needed (e.g. by using malloc);
2. Mess with the memory allocated.
(C++ took this one step further by defining class-specific allocators,
feature that D copied. That turned out to be little else than a lateral
step. C++ also offers distinct allocation for arrays vs. anything else,
but because it lacks typed reallocation primitives, it effectively
hamstrung that feature's capabilities. Also the STL introduced
allocators, which turned out to not do much of anything useful except
being an immense time sink for everyone involved with them in any
capacity. I call these cumulatively The Big Distraction.)
I've just had a mini-epiphany that's been buzzing around my head for a
while. Finally it got to a form expressible in words:
====
Type should inform allocation.
====
I.e. you shouldn't first allocate and then brand the memory with a type.
Instead, you should make the type known _during_ the allocation process.
This is not new and on the face of it not even all that noteworthy: (a)
some high-level languages did this for years, (b) it's unclear which
exact properties of a type should be relevant to the allocation.
Within the context of D, there are some interesting aspects of a type
that a complex modular allocator could use to great effect. Consider:
1. Individual objects (i.e. not arrays)
When allocating an individual object, there is virtually zero chance
that object will ever need to be resized. (There are exceptions such as
"the struct hack" but those would be handled together with arrays.)
There are two important consequences of this:
(a) Individual object sizes are already quantized, i.e. there is a
relatively small set of distinct sizes compared to the number of objects
being allocated.
(b) Individual objects can be placed in an allocator that's arbitrarily
adverse to reallocation (i.e. has no in-place expansion ability and no
clever reallocation primitives). It seems like FreeTree
(file:///Users/aalexandre/code/d/dlang.org/web/phobos-prerelease/std_experimental_allocator_free_tree.html)
would be an excellent fit for allocating individual objects. HeapBlock
also comes to mind.
2. Arrays
The range of sizes allocated for arrays is quite a bit larger and more
arbitrary than for individual objects. Arrays still grow in quanta (e.g.
T.sizeof hops) but the set of distinct sizes is much larger and much
less predictable.
One other interesting thing is that arrays offer concatenation and
resizing as primitive operations, so it follows that their underlying
allocator should be friendly to such. This leads to an allocator design
for arrays that's radically different from the allocator design for
individual objects.
Long story short, arrays should sit on a different heap than objects.
3. Thread-local vs. shared objects
Currently in D it's legal to allocate memory in one thread and
deallocate it in another. (One simple way to look at it is casting to
shared.) This has a large performance cost that only benefits very few
actual cases.
It follows that we need to change the notion that you first allocate
memory and then brand it as shared. The "will be shared" knowledge must
be present during allocation, and use different methods of allocation
for the two cases.
4. "Has pointers" vs. "has no pointers"
When collecting a specific object, it's important to know whether its
type embeds pointers. If it does, more scanning is necessary. Otherwise,
the object is a "leaf" leading to no others.
It seems to me we stand to gain by physically and conceptually
separating memory that stores leaf objects from that dedicated to
non-leaf objects. Making the scan-heavy memory more compact leads to
better cache friendliness.
Currently D's allocator allows choosing at runtime for each allocated
block whether is should be scanned. The new design would require making
the choice upfront. There would be, of course, the "anything goes" heap
that still allows that level of dynamism.
5. "Plan to deallocate" vs. "plan to let the GC mind this"
Objects that will be deallocated manually deserve different placement
compared to those that will only be deallocated during a GC cycle.
6. Immutable vs. mutable
I'm not sure how this can be practically exploited. There must be
something in the notion that, save for a brief write period after
allocation, the memory will stay unmodified. Still thinking.
7. Strings
On the face of it strings are immutable arrays, so they've been already
discussed. However, they have some interesting characteristics:
(a) small alignment, e.g. 1 byte
(b) often extremely short, e.g. 1-8 bytes
(c) concatenation intensive (including append)
(d) perhaps other unique properties and patterns that elude me
So... types should inform allocation.
Please chime in!
Andrei
