On 9/24/13 1:46 AM, Dmitry Olshansky wrote:
23-Sep-2013 03:49, Andrei Alexandrescu пишет:
Looks good (s/ubyte[]/void[] per current discussion).
Changed.
Do you imagine Typed allocators as something more then adapters that
simplify a common pattern of allocate + emplace / destroy + deallocate?
(create!T/destroy!T)
Well as a simple matter tracing allocators will have to store dynamic
type information (just like the current GC does).
Also, I hope we'll be able to allow allocators to define Pointer(T),
Ref(T) etc. that supplant replacements for the built-in notions of
pointer, reference etc. Then, user code that uses these notions instead
of the built-in ones will be guaranteed some nice properties (e.g.
automatic reference counting). Unfortunately I don't see a way for an
allocator to enforce that its users don't do illegal things such as
escaping addresses etc. So it would be a discipline-backed scheme.
Notable beneficiaries will be containers.
First things first - can't allocator return alignment as run-time value
- a property (just like 'available' does)? The implementation contract
is that it must be O(1) vanila syscall-free function. (Read this as
consult system info exactly once, at construction).
It could, but as I mentioned to Manu - at this level any cost is
significant. Even changing from a compile-time constant to a global
static dynamically-initialized constant has a cost. Making alignment an
instance variable turns stateless allocators into stateful ones.
Thinking more of it - it also may be immutable size_t? Then it gets
proper value at construction and then is never changed.
I'm hoping to get away with a static function "static uint alignment()"
that (a) is CTFEable for most allocators/platforms, (b) uses a
dynamically-initialized static constant for a few. Then derived
allocators will inherit CTFEability.
Would a per-allocator-type alignment suffice?
* deallocate(b) deallocates the memory allocated for b. b must have been
previously allocated by the same allocator. This method is usually
unsafe (but there are notable implementations that may offer safety,
such as unbounded freelists.) This method is optional.
Does the following implication hold "have a deallocate" --> must be
manually managed? Otherwise how would one reliably work with it and not
leak? This brings us to traits that allocators may (should) have
a-la automatic? free-all on termination? Zeros on allocate (more common
then one would think)? etc.
The global GC does offer manual deallocation. It's the presence of
collect() that indicates tracing abilities. If deallocateAll() is
present, user code must assume it will be called during destruction.
That said, I've also been thinking of adding a variety of Boolean
telling properties. "Zeros on allocate" has an important relationship
with safety of higher-level objects - zeros offer "not really
initialized but without forged pointers so memory-safe" objects.
* deallocateAll() deallocates in one shot all memory previously
allocated by this allocator. This method is optional, and when present
is almost always unsafe (I see no meaningful @safe implementation.)
Region allocators are notable examples of allocators that define this
method.
Okay.. I presume region "mark" works by spiting off a subinstance of
allocator and "release" by deallocateAll().
Nice, didn't think of this.
* collect() frees unused memory that had been allocated with this
allocator. This optional method is implemented by tracing collectors and
is usually @safe.
This seems hard and/or suboptimal w/o typeinfo --> typed allocators? I
guess they could be more then a simple helper.
Yah, collect() is not really appropriate at this level...
There are quite a few more things to define more precisely, but this
part of the design has become quite stable. To validate the design, I've
defined some simple allocators (Mallocator, GCAllocator, Freelist,
StackRegion, Region etc) but not the more involved ones, such as
coalescing heaps, buddy system etc.
The problem I see is that allocators are rooted in poor foundation -
malloc is so out of fashion (its interface is simply too thin on
guarantees), sbrk is frankly a stone-age syscall.
I would love to make a root allocator one on top of mmap/VirtualAlloc.
This leads me to my biggest problem with classical memory management -
~20 years of PCs having virtual memory support directly in the CPU, and
yet hardly anything outside of OS takes advantage of it. They
(allocators) seem simply not aware of it - none of interface implies
anything that would help user take advantage of it. I'm talking of
(potentially) large allocations that may be often resized.
(large allocations actually almost always a blind spot/fallback in
allocators)
To the point - we have address space and optionally memory committed in
there, leading us to a 3-state of an _address range_:
available, reserved, committed. The ranges of 2nd state are dirt cheap
(abundant on 64bit) and could be easily flipped to committed and back.
So I have a pattern I want to try to fit in your design. At present it
is a datastructure + allocation logic. What I would want is clean and
nice composition for ultimate reuse.
[snip]
Interesting. I'll be looking forward to what you come up with. Yes, for
large, coarse-granularity allocations, tapping into OS' paging
capabilities is the best way to go.
Now how to fit this monster into the current API...
Plainly I need a way to tell hey Mr. Allocator RESERVE me a 1Gb of RAM
but don't chew on, it please. In other words - allocate needs something
like a "guaranteed capacity of the block". By default it could be == size.
struct Allocator
{
...
//allocate size bytes with a block of with no less then capacity bytes.
void[] allocate(size_t size, size_t capacity=size);
...
}
Or maybe somehow add a reserve method explicitly...
Assuming you have an optional two-argument allocate() primitive, once
you get the initial allocation, how do you commit it? By calling
expand() I assume? Would that be enough?
In the reserve()-based API - how would that work? Does reserve returns a
void[] with size zero and then you expand() it?
Andrei
