On 10/24/13 12:54 PM, Andrei Alexandrescu wrote:
> Hello,
>
>
> I know it's been a long wait. Hopefully it was worth it. The alpha
> release of untyped allocators is ready for tire-kicking and a test drive.
>
> Code: https://github.com/andralex/phobos/blob/allocator/std/allocator.d
>
> Dox: http://erdani.com/d/phobos-prerelease/std_allocator.html

Added SharedFreelist, a lock-free freelist.

http://erdani.com/d/phobos-prerelease/std_allocator.html#.SharedFreelist


Andrei

On 10/31/13 7:26 PM, safety0ff wrote:
> I noticed that the GCAllocator provides no way of controlling the memory
> block attributes (http://dlang.org/phobos/core_memory.html#.GC.BlkAttr
> ,) all allocations get the default (no attributes.) This is a leaky
> abstraction, a data structure or composed allocators may desire to
> control the attributes to reduce GC pressure.

These attributes seem to be informed by the types stored, which would be above the charter of untyped allocator.

Andrei

On Friday, 1 November 2013 at 02:43:00 UTC, Andrei Alexandrescu wrote:
> On 10/31/13 7:26 PM, safety0ff wrote:
>> I noticed that the GCAllocator provides no way of controlling the memory
>> block attributes (http://dlang.org/phobos/core_memory.html#.GC.BlkAttr
>> ,) all allocations get the default (no attributes.) This is a leaky
>> abstraction, a data structure or composed allocators may desire to
>> control the attributes to reduce GC pressure.
>
> These attributes seem to be informed by the types stored, which would be above the charter of untyped allocator.
>
> Andrei

The choice is for the typed allocator. That mean that untyped allocator should either provide the choice, or assume the worse (it may contain pointer).

On Friday, 1 November 2013 at 02:43:00 UTC, Andrei Alexandrescu wrote:
> On 10/31/13 7:26 PM, safety0ff wrote:
>> I noticed that the GCAllocator provides no way of controlling the memory
>> block attributes (http://dlang.org/phobos/core_memory.html#.GC.BlkAttr
>> ,) all allocations get the default (no attributes.) This is a leaky
>> abstraction, a data structure or composed allocators may desire to
>> control the attributes to reduce GC pressure.
>
> These attributes seem to be informed by the types stored, which would be above the charter of untyped allocator.
>
> Andrei

The attributes are informed by whatever code is calling the GC, the GC interface deals in void*'s.

Consider an AA implementation that wishes to use FancyAllocator with fallback GCAllocator with block attributes NO_INTERIOR and NO_SCAN.
With your proposed GCAllocator you either need to rewrite GCAllocator, or you need to add some nasty code to set the attributes depending on whether the primary allocator or secondary allocator own the memory.

By fixing the leaky abstraction this use case can be coded as follows:
FallbackAllocator!(FancyAllocator, GCAllocator!(GC.BLkAttr.NO_INTERIOR | GC.BLkAttr.NO_SCAN)) a;

On 10/31/13 8:37 PM, safety0ff wrote:
> On Friday, 1 November 2013 at 02:43:00 UTC, Andrei Alexandrescu wrote:
>> On 10/31/13 7:26 PM, safety0ff wrote:
>>> I noticed that the GCAllocator provides no way of controlling the memory
>>> block attributes (http://dlang.org/phobos/core_memory.html#.GC.BlkAttr
>>> ,) all allocations get the default (no attributes.) This is a leaky
>>> abstraction, a data structure or composed allocators may desire to
>>> control the attributes to reduce GC pressure.
>>
>> These attributes seem to be informed by the types stored, which would
>> be above the charter of untyped allocator.
>>
>> Andrei
>
> The attributes are informed by whatever code is calling the GC, the GC
> interface deals in void*'s.
>
> Consider an AA implementation that wishes to use FancyAllocator with
> fallback GCAllocator with block attributes NO_INTERIOR and NO_SCAN.
> With your proposed GCAllocator you either need to rewrite GCAllocator,
> or you need to add some nasty code to set the attributes depending on
> whether the primary allocator or secondary allocator own the memory.
>
> By fixing the leaky abstraction this use case can be coded as follows:
> FallbackAllocator!(FancyAllocator, GCAllocator!(GC.BLkAttr.NO_INTERIOR |
> GC.BLkAttr.NO_SCAN)) a;

Migrating the flags into the type is a possibility but maybe it's easiest to add flags as runtime parameters.

Allocators can always define additional nonstandard routines. The standard routines concern mostly composition.

Of course, it is also possible to make such flags standard (it may be the case that typed allocators require such).


Andrei

On Friday, 1 November 2013 at 15:15:10 UTC, Andrei Alexandrescu wrote:
> Migrating the flags into the type is a possibility but maybe it's easiest to add flags as runtime parameters.

I was using that as an example to argue for its inclusion because it was concise.

I'm not sure what the best interface would be, I'd have to think about it for a while.

On 11/01/2013 03:34 AM, Andrei Alexandrescu wrote:
> Added SharedFreelist, a lock-free freelist.
>
> http://erdani.com/d/phobos-prerelease/std_allocator.html#.SharedFreelist
>
>
> Andrei

Nice, that reminds me that I still want to polish my implementation of a lock free doubly-linked list in D.
It would be great to collect these efforts in a library.
I remember the request of Adam Wilson for a System.Collections.Concurrent in D.
I put my stuff on github https://github.com/dawgfoto/lock-free.

The doubly-linked list is based on this paper. IIRC the paper had a bug.
http://dx.doi.org/10.1016/j.jpdc.2008.03.001

Recently I also found a C++ implementation. It's much simpler in D due to the GC.
https://github.com/Kometes/Honeycomb/blob/master/src/common/Honey/Thread/LockFree/List.h

I have another request despite putting this in it's own repo.

Often one want an exponentially (power of 2) growing step size for Bucketizer. Currently only equally spaced buckets are possible which isn't very practical to scale from 16b to 2Mb.
http://erdani.com/d/phobos-prerelease/std_allocator.html#.Bucketizer

On 10/30/13 1:02 PM, Martin Nowak wrote:
> This looks really promising.
> There are a lot of building blocks and the way different capabilities
> are modelled by optional methods nicely solves the biggest difficulty
> with allocators.
> I think it's important to put this in it's own github repo and add a dub
> package for it on code.dlang.org so that it's easy to test the
> implementation and to contribute improvements.

Tried to register github package andralex/phobos, and:

============================
500 - Internal Server Error

Internal Server Error

Internal error information:
object.Exception@source/dubregistry/repositories/repository.d(43): Failed to read JSON from https://raw.github.com/andralex/phobos/master/package.json: Unexpected reply for 'https://raw.github.com/andralex/phobos/master/package.json': Not Found
----------------
./dub-registry(dubregistry.repositories.repository.PackageVersionInfo dubregistry.repositories.github.GithubRepository.getVersionInfo(immutable(char)[])+0x3b5) [0x6e8ec1]
./dub-registry(void dubregistry.registry.DubRegistry.addPackage(vibe.data.json.Json, vibe.data.bson.BsonObjectID)+0xa6) [0x62d372]
./dub-registry(void dubregistry.web.DubRegistryWebFrontend.addPackage(vibe.http.server.HTTPServerRequest, vibe.http.server.HTTPServerResponse, userman.controller.User)+0x222) [0x6e4406]
./dub-registry(void delegate(vibe.http.server.HTTPServerRequest, vibe.http.server.HTTPServerResponse) userman.web.UserManWebInterface.auth(void delegate(vibe.http.server.HTTPServerRequest, vibe.http.server.HTTPServerResponse, userman.controller.User)).void requestHandler(vibe.http.server.HTTPServerRequest, vibe.http.server.HTTPServerResponse)+0x10d) [0x800181]
./dub-registry(void vibe.http.router.URLRouter.handleRequest(vibe.http.server.HTTPServerRequest, vibe.http.server.HTTPServerResponse)+0x179) [0x6fb8b5]
./dub-registry(bool vibe.http.server.handleRequest(vibe.core.stream.Stream, immutable(char)[], vibe.http.server.HTTPServerListener, ref vibe.http.server.HTTPServerSettings, ref bool)+0x16c8) [0x6f0344]
./dub-registry(void vibe.http.server.handleHTTPConnection(vibe.core.net.TCPConnection, vibe.http.server.HTTPServerListener)+0x143) [0x6eebb7]
./dub-registry(void vibe.http.server.listenHTTPPlain(vibe.http.server.HTTPServerSettings, void delegate(vibe.http.server.HTTPServerRequest, vibe.http.server.HTTPServerResponse)).void doListen(vibe.http.server.HTTPServerSettings, vibe.http.server.HTTPServerListener, immutable(char)[]).void __lambda54(vibe.core.net.TCPConnection)+0x2c) [0x6eb160]
./dub-registry(extern (C) nothrow void vibe.core.drivers.libevent2_tcp.onConnect(int, short, void*).void ClientTask.execute()+0x2d6) [0x70939a]
./dub-registry(void vibe.core.core.CoreTask.run()+0xf2) [0x7172fe]
./dub-registry(void core.thread.Fiber.run()+0x2a) [0x83eae2]
./dub-registry(fiber_entryPoint+0x61) [0x83e9ed]
[(nil)]
============================

This is obviously because package.json is absent from the repo, but I'd say it shouldn't cause such an error.

That makes me think probably Phobos should have a package.json so people can install updates via code.dlang.org.

> That said it failed my litmus test.
> I previously used David Simcha's RegionAllocator
> https://github.com/dsimcha/TempAlloc/blob/master/std/allocators/region.d.

Let's see!

> The pattern is to allocate some metadata followed by allocating many
> fixed size tree nodes. When the tree is constructed it is used to render
> an image which is the result of that operation.
> The tree and all metadata is freed and the region allocator is reused
> for the next method invocation (it keeps the memory).
>
> I think the closest would be to use CascadingAllocator with Region but
> there are two issues.
>
> CascadingAllocator successively tries all allocators and if that fails
> creates a new region. So this runs in O(N) complexity even though most
> of the time only the last allocator will have memory available.

Yah, I'd left a TODO in there when I first wrote the code:

https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L3723

The newly-added allocator should come to the front of the list.

My suspicion, however, is that you won't be able to measure a difference. A well-dimensioned cascade of regions will have a high ration of allocations within a regions to number of regions.

> There is no simple way to deallocateAll without freeing the regions.
> What I need is something similar to clear in appender.

Hm, interesting. But then again - do you think it makes a difference? Allocation of regions is a very small fraction of the work done on using the regions.

> I also can't relinquish the memory from the inner regions because they
> are private.

How do we formalize that?

> So for my use-case the only way that I found to use this module
> is to compute the upper bound of memory needed when the renderer is
> invoked. Then I have to relinquish the buffer from a region, reallocate
> it using Mallocator.it and construct a new region with the reallocated
> buffer.

I'd say just plow ahead with a straight region as implemented. If you measure any difference, let's talk.


Andrei

On 11/1/13 1:36 PM, Martin Nowak wrote:
> I have another request despite putting this in it's own repo.

I assume s/despite/in addition to/ :o).

> Often one want an exponentially (power of 2) growing step size for
> Bucketizer. Currently only equally spaced buckets are possible which
> isn't very practical to scale from 16b to 2Mb.
> http://erdani.com/d/phobos-prerelease/std_allocator.html#.Bucketizer

I considered the growth strategy as a policy. My personal favorite is "choose an approximate exponential growth strategy that keeps maximum internal fragmentation less than x%." That's how jemalloc is dimensioned.

I decided to stick with linear at least for now, for a simple reason: it's easy enough to simply enumerate the strategy by hand by using Segregator. Exponentials quickly grow to span a bunch of memory, so there aren't a lot of terms involved. Nevertheless it would be a nice illustration of D's generative powers.


Andrei