www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - FYI - mo' work on std.allocator

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Added SbrkRegion, SimpleBlocklist, and Blocklist.

http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

Destruction is as always welcome. I plan to get into tracing tomorrow 
morning.


Andrei
Apr 26 2014
next sibling parent reply "Brian Schott" <briancschott gmail.com> writes:
On Sunday, 27 April 2014 at 05:43:07 UTC, Andrei Alexandrescu 
wrote:
 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.


 Andrei

There are quite a few places where functions could be marked pure, nothrow, safe, or trusted that have not been. I have a pull request open for many of these. I also have a feature request. I think something like this should be added to std.allocator: /** * Shortcut that encapsulates a cast and a call to emplace() * Params: * a = the allocator to use * args = the arguments to $(D T)'s constructor * Returns: a pointer to an instance of $(D T). */ T* allocate(T, Allocator, Args...)(auto ref Allocator a, auto ref Args args) trusted if (is (T == struct)) { import std.conv : emplace; void[] mem = a.allocate(T.sizeof); return emplace(cast(T*) mem.ptr, args); } The allocate-cast-initialize pattern is incredibly common in the code that I've written using allocators so far and I'd like it to be in Phobos so that it does not need to be re-implemented everywhere.
Apr 26 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/26/14, 11:13 PM, Brian Schott wrote:
 There are quite a few places where functions could be marked pure,
 nothrow,  safe, or  trusted that have not been. I have a pull request
 open for many of these.

Thanks!
 I also have a feature request. I think something like this should be
 added to std.allocator:

 /**
   * Shortcut that encapsulates a cast and a call to emplace()
   * Params:
   * a = the allocator to use
   * args = the arguments to $(D T)'s constructor
   * Returns: a pointer to an instance of $(D T).
   */
 T* allocate(T, Allocator, Args...)(auto ref Allocator a, auto ref Args
 args)
       trusted if (is (T == struct))
 {
      import std.conv : emplace;
      void[] mem = a.allocate(T.sizeof);
      return emplace(cast(T*) mem.ptr, args);
 }

 The allocate-cast-initialize pattern is incredibly common in the code
 that I've written using allocators so far and I'd like it to be in
 Phobos so that it does not need to be re-implemented everywhere.

Totally. That will be part of typed allocators, module that's now empty :o). Andrei
Apr 27 2014
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
I have a question regarding `owns`:

     bool owns(void[] b);

The documentation states it should return true if b has been 
allocated with this allocator. But what should happen if a 
sub-slice of an allocated object is passed? Or when a slice is 
passed that contains/overlaps an object belonging to the 
allocator?
Apr 27 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/27/14, 3:58 AM, "Marc Schütz" <schuetzm gmx.net>" wrote:
 I have a question regarding `owns`:

      bool owns(void[] b);

 The documentation states it should return true if b has been allocated
 with this allocator. But what should happen if a sub-slice of an
 allocated object is passed? Or when a slice is passed that
 contains/overlaps an object belonging to the allocator?

Behavior is dependent on the allocator. Only full blocks (returned by allocate()) are guaranteed. -- Andrei
Apr 27 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/27/14, 4:13 AM, "Marc Schütz" <schuetzm gmx.net>" wrote:
 Also, there is an `expand()` method, but no `shrink()`. Is that an
 oversight, or intentional?

I tried to avoid it because it's error-prone. reallocate() should shrink in place where appropriate. But I'll add it if it turns out it's necessary. Andrei
Apr 27 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
Also, there is an `expand()` method, but no `shrink()`. Is that 
an oversight, or intentional?
Apr 27 2014
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Sunday, 27 April 2014 at 11:13:42 UTC, Marc Schütz wrote:
 Also, there is an `expand()` method, but no `shrink()`. Is that 
 an oversight, or intentional?

If I remember correctly, this was discussed in the initial review of Andrei's proposal (just search the NG for std.allocator). David
Apr 27 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 27 April 2014 at 13:10:42 UTC, David Nadlinger wrote:
 On Sunday, 27 April 2014 at 11:13:42 UTC, Marc Schütz wrote:
 Also, there is an `expand()` method, but no `shrink()`. Is 
 that an oversight, or intentional?

If I remember correctly, this was discussed in the initial review of Andrei's proposal (just search the NG for std.allocator). David

Thanks, found it. The argument was that shrink can not be safe [1], but Andrei wasn't opposed to adding it if desired [2]. [1] http://forum.dlang.org/thread/l1nvn4$ca3$1 digitalmars.com?page=1 [2] http://forum.dlang.org/post/l1st99$10ug$1 digitalmars.com
Apr 27 2014
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.

How easy is to implement a OS-portable (disk-backed) virtual memory scheme using std.allocator? :-) Is it a good idea to include one such scheme in std.allocator? Bye, bearophile
Apr 27 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/27/14, 7:51 AM, bearophile wrote:
 Andrei Alexandrescu:

 Destruction is as always welcome. I plan to get into tracing tomorrow
 morning.

How easy is to implement a OS-portable (disk-backed) virtual memory scheme using std.allocator? :-) Is it a good idea to include one such scheme in std.allocator? Bye, bearophile

I just added MmapAllocator: http://erdani.com/d/phobos-prerelease/std_allocator.html#.MmapAllocator If anyone would like to add a Windows implementation, that would be great. Andrei
Apr 27 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/27/14, 9:21 AM, bearophile wrote:
 Andrei Alexandrescu:

 I just added MmapAllocator:

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

 If anyone would like to add a Windows implementation, that would be
 great.

So it's not using this portable module? http://dlang.org/phobos/std_mmfile.html

That's a class, so it would need its own allocation etc. Too much trouble. -- Andrei
Apr 27 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/4/14, 8:06 PM, Marco Leise wrote:
 Virtual memory allocators seem obvious, but there are some
 details to consider.

 1) You should not hard code the allocation granularity in the
     long term. It is fairly easy to get it on Windows and Posix
     systems:

 On Windows:
    SYSTEM_INFO si;
    GetSystemInfo(&si);
    return si.allocationGranularity;

 On Posix:
    return sysconf(_SC_PAGESIZE);

I've decided that runtime-chosen page sizes are too much of a complication for the benefits.
 2) For embedded Linux systems there is the flag
     MAP_UNINITIALIZED to break the guarantee of getting
     zeroed-out memory. So if it is desired, »zeroesAllocations«
     could be a writable property there.

This can be easily done, but from what MAP_UNINITIALIZED is strongly discouraged and only implemented on small embedded systems.
 In the cases where I used virtual memory, I often wanted to
 exercise more of its features. As it stands now »MmapAllocator«
 works as a basic allocator for 4k blocks of memory. Is that
 the intended scope or are you open to supporting all of it?

For now I just wanted to get a basic mmap-based allocator off the ground. I am aware there's a bunch of things to do. The most prominent is that (according to Jason Evans) Linux is pretty bad at munmap() so it's actually better to advise() pages away upon deallocation but never unmap them. Andrei
May 04 2014
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
05-May-2014 20:57, Marco Leise пишет:
 That sounds like a more complicated topic than anything I had
 in mind. I think a »std.virtualmemory« module should already
 implement all the primitives in a portable form, so we don't
 have to do that again for the next use case. Since
 cross-platform code is always hard to get right, it could also
 avoid latent bugs.

I had an idea of core.vmm. It didn't survive the last review though, plus I never got around to test OSes aside from Windows & Linux. Comments on initial design are welcome. https://github.com/D-Programming-Language/druntime/pull/653 -- Dmitry Olshansky
May 05 2014
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
06-May-2014 10:20, Marco Leise пишет:
 Am Mon, 05 May 2014 21:13:10 +0400
 schrieb Dmitry Olshansky <dmitry.olsh gmail.com>:

 05-May-2014 20:57, Marco Leise пишет:
 That sounds like a more complicated topic than anything I had
 in mind. I think a »std.virtualmemory« module should already
 implement all the primitives in a portable form, so we don't
 have to do that again for the next use case. Since
 cross-platform code is always hard to get right, it could also
 avoid latent bugs.

I had an idea of core.vmm. It didn't survive the last review though, plus I never got around to test OSes aside from Windows & Linux. Comments on initial design are welcome. https://github.com/D-Programming-Language/druntime/pull/653

That's exactly what I had in mind and more. :)

Cool. I was ambitious at start until I released that there were about 5-6 logically consistent primitives of which many OS-es provided say 3 or 4 with little or inexact overlap. That's why I thought of focusing on common recipes, and provide building blocks for them.
 These are all free functions that can be used as building
 blocks for more specific objects. Was there a dedicated review
 thread on the news group? All I could find was a discussion
 about why not to use a VMM struct with static functions as
 a namespace replacement.

I don't recall such but I think I did a tiny topic on it in general D NG. -- Dmitry Olshansky
May 06 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/5/14, 9:57 AM, Marco Leise wrote:
 That sounds like a more complicated topic than anything I had
 in mind. I think a »std.virtualmemory« module should already
 implement all the primitives in a portable form, so we don't
 have to do that again for the next use case. Since
 cross-platform code is always hard to get right, it could also
 avoid latent bugs.
 That module would also offer functionality to get the page
 size and allocation granularity and wrappers for common needs
 like getting n KiB of writable memory. Management however
 (i.e. RAII structs) would not be part of it.
 It sounds like not too much work with great benefit for a
 systems programming language.

I think adding portable primitives to http://dlang.org/phobos/std_mmfile.html (plus better yet refactoring its existing code to use them) would be awesome and wouldn't need a DIP. -- Andrei
May 05 2014
prev sibling next sibling parent "Kagamin" <spam here.lot> writes:
On Sunday, 27 April 2014 at 06:13:22 UTC, Brian Schott wrot
 T* allocate(T, Allocator, Args...)(auto ref Allocator a, auto 
 ref Args args)
      trusted if (is (T == struct))
 {

Though, it's not trusted.
Apr 27 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 I just added MmapAllocator:

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

 If anyone would like to add a Windows implementation, that 
 would be great.

So it's not using this portable module? http://dlang.org/phobos/std_mmfile.html Bye, bearophile
Apr 27 2014
prev sibling next sibling parent "Guillaume Chatelet" <chatelet.guillaume gmail.com> writes:
On Sunday, 27 April 2014 at 16:01:55 UTC, Andrei Alexandrescu 
wrote:
 I just added MmapAllocator:

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

 If anyone would like to add a Windows implementation, that 
 would be great.


 Andrei

This could come in handy https://code.google.com/p/mman-win32/source/browse/#svn%2Ftrunk Guillaume
Apr 27 2014
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Added a bunch more stuff:

* new optional primitives:

- empty() returns true if no current allocation

- zeroesAllocations is true if the allocator automatically sets freshly 
allocated memory to zero

- resolveInternalPointer(p) gives the allocated block corresponding to p

* An interesting internal type EmbeddedTree: a binary search tree that 
can be threaded within memory blocks making them more searchable.

* A type WithInternalPointers that uses an EmbeddedTree to implement 
resolveInternalPointer.

* Default implementation of alignedReallocate.

* Improved the sbrk-based region.

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

The name WithInternalPointers is rather goofy - ideas?

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



Andrei
Apr 27 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 - zeroesAllocations is true if the allocator automatically sets 
 freshly allocated memory to zero

In some cases there is a need for a certain zeroing, even when memory is deallocated: https://issues.dlang.org/show_bug.cgi?id=10661 This can be added. In some case there is also a need to track and tell apart tainted/untainted memory zones.
 The name WithInternalPointers is rather goofy - ideas?

Inner? Bye, bearophile
Apr 27 2014
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 27 Apr 2014 01:43:08 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing tomorrow  
 morning.

First time I've seen it, so I'm looking at everything. In the design docs: alignedAllocate(size_t s, uint a);, $(RES) is null || $(RES).length == s) $(TD Similar to $(D allocate), with the additional guarantee that the memory returned is aligned to at least $(D a) bytes. $(D a) must be a power of 2 greater than $(D (void*).sizeof).)) Why power of 2 greater than void*.sizeof? Seems like an extra check that isn't necessary. Consider that any block that is aligned to a power of 2 called N, it's also aligned by any power of 2 < N. I think specifying any power of 2 is fine (including 1!). If anything, a maximum power of 2 may be good, because that's not as easy to ensure. -Steve
Apr 28 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/28/14, 6:34 AM, Steven Schveighoffer wrote:
 On Sun, 27 Apr 2014 01:43:08 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing tomorrow
 morning.

First time I've seen it, so I'm looking at everything. In the design docs: alignedAllocate(size_t s, uint a);, $(RES) is null || $(RES).length == s) $(TD Similar to $(D allocate), with the additional guarantee that the memory returned is aligned to at least $(D a) bytes. $(D a) must be a power of 2 greater than $(D (void*).sizeof).)) Why power of 2 greater than void*.sizeof? Seems like an extra check that isn't necessary. Consider that any block that is aligned to a power of 2 called N, it's also aligned by any power of 2 < N. I think specifying any power of 2 is fine (including 1!). If anything, a maximum power of 2 may be good, because that's not as easy to ensure.

Fair enough, I'll remove that part of the spec. Thanks! -- Andrei
Apr 28 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/1/14, 3:36 AM, Temtaime wrote:
 Hi Andrey. Have you even test your allocator on different arch(32/64)
 and/or with different compiler flags ?

Thanks, I'll look into that! -- Andrei
May 01 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/5/14, 12:13 AM, safety0ff wrote:
 On Monday, 28 April 2014 at 16:03:33 UTC, Andrei Alexandrescu wrote:
 Fair enough, I'll remove that part of the spec. Thanks! -- Andrei

According to the docs, the "multiple of sizeof(void*)" restriction only applies to posix_memalign (and not to _aligned_malloc and aligned_alloc.)

Well I've changed the docs recently, so if they're good now, excellent.
 I've decided that runtime-chosen page sizes are too much of a
 complication for the benefits.

Do the complications arise in the MmapAllocator or the higher level allocators?

The latter, which make compile-time decisions based on alignment.
 I'd like to see a Windows allocator based on VirtualAlloc, and
 afterwards a "SystemAllocator" defined to be MmapAllocator on unix-based
 and VirtualAlloc based on Windows.
 This "SystemAllocator" would ideally have an allocationGranularity
 property.

Properties that don't need to propagate are easier to accommodate. Andrei
May 05 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Sunday, 27 April 2014 at 05:43:07 UTC, Andrei Alexandrescu 
wrote:
 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.


 Andrei

Nothing much to add here, I just wanted to say that I'm very excited to see the wider consequences of this module/design.
Apr 28 2014
prev sibling next sibling parent "Temtaime" <temtaime gmail.com> writes:
Hi Andrey. Have you even test your allocator on different 
arch(32/64) and/or with different compiler flags ?

On Windows, 32 bit.

dmd allocator.d -main

allocator.d(1492): Error: cannot implicitly convert expression (x 
/ 64LU) of typ
e ulong to immutable(uint)
allocator.d(1494): Error: cannot implicitly convert expression (y 
/ 64LU) of typ
e ulong to immutable(uint)
allocator.d(1518): Error: cannot implicitly convert expression (x 
/ 64LU) of typ
e ulong to uint
allocator.d(1524): Error: cannot implicitly convert expression 
(i) of type ulong
  to uint
allocator.d(1525): Error: cannot implicitly convert expression 
(i) of type ulong
  to uint
allocator.d(1542): Error: cannot implicitly convert expression 
(w) of type ulong
  to uint
allocator.d(1551): Error: cannot implicitly convert expression 
(w) of type ulong
  to uint
allocator.d(1570): Error: cannot implicitly convert expression 
(w) of type ulong
  to uint
allocator.d(1580): Error: cannot implicitly convert expression 
(w) of type ulong
  to uint
allocator.d(1596): Error: cannot implicitly convert expression 
(x) of type ulong
  to uint
allocator.d(1596): Error: cannot implicitly convert expression 
(y) of type ulong
  to uint

If i fix these errors it's ok, but not ok with unittests.

dmd allocator.d -main -debug -unittest

allocator.d(4042): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4082): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(2123): Error: template instance 
std.allocator.InSituRegion!(10240, 6
4) error instantiating
allocator.d(2391): Error: cannot implicitly convert expression 
(4096LU * i) of t
ype ulong to uint
allocator.d(2391): Error: cannot implicitly convert expression 
(4096LU * j) of t
ype ulong to uint
allocator.d(6513): Error: template instance 
std.traits.hasMember!(HeapBlockWithI
nternalPointers!4096, "resolveInternalPointer") error 
instantiating
allocator.d(2266):        instantiated from here: 
testAllocator!(delegate () =>
(HeapBlockWithInternalPointers!4096 __ctmp2115 = 0;
  , __ctmp2115).this(m))
allocator.d(2439):        instantiated from here: 
HeapBlockWithInternalPointers!
4096
allocator.d(4042): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4082): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(2740): Error: template instance 
std.allocator.InSituRegion!16384 err
or instantiating
allocator.d(3838): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(3882): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(3993): Error: template instance 
std.allocator.Region!() error instan
tiating
allocator.d(4042): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4082): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4135): Error: template instance 
std.allocator.InSituRegion!(131072,
64) error instantiating
allocator.d(4042): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4082): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4140): Error: template instance 
std.allocator.InSituRegion!131072 er
ror instantiating
allocator.d(4042): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4082): Error: function 
std.allocator.roundUpToMultipleOf (uint s, ui
nt base) is not callable using argument types (ulong, uint)
allocator.d(4161): Error: template instance 
std.allocator.InSituRegion!4096 erro
r instantiating
May 01 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 01 May 2014 08:01:43 -0700
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 On 5/1/14, 3:36 AM, Temtaime wrote:
 Hi Andrey. Have you even test your allocator on different arch(32/64)
 and/or with different compiler flags ?

Thanks, I'll look into that! -- Andrei

If size_t was a distinct type ... just thinking loudly. -- Marco
May 04 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Sun, 27 Apr 2014 09:01:58 -0700
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 On 4/27/14, 7:51 AM, bearophile wrote:
 Andrei Alexandrescu:

 Destruction is as always welcome. I plan to get into tracing tomorrow
 morning.

How easy is to implement a OS-portable (disk-backed) virtual memory scheme using std.allocator? :-) Is it a good idea to include one such scheme in std.allocator? Bye, bearophile

I just added MmapAllocator: =20 http://erdani.com/d/phobos-prerelease/std_allocator.html#.MmapAllocator =20 If anyone would like to add a Windows implementation, that would be great. =20 =20 Andrei

Virtual memory allocators seem obvious, but there are some details to consider. 1) You should not hard code the allocation granularity in the long term. It is fairly easy to get it on Windows and Posix systems: On Windows: SYSTEM_INFO si; GetSystemInfo(&si); return si.allocationGranularity; On Posix: return sysconf(_SC_PAGESIZE); 2) For embedded Linux systems there is the flag MAP_UNINITIALIZED to break the guarantee of getting zeroed-out memory. So if it is desired, =C2=BBzeroesAllocations=C2=AB could be a writable property there. In the cases where I used virtual memory, I often wanted to exercise more of its features. As it stands now =C2=BBMmapAllocator=C2=AB works as a basic allocator for 4k blocks of memory. Is that the intended scope or are you open to supporting all of it? =46rom the top of my head there is: - committing/decommitting ranges of memory - setting protection attributes - remapping virtual memory pages to other physical pages Each allows some use cases, that I could expand on if you want. So it would be beneficial in any case to have those primitives in a portable form in Phobos. The question is, should that place be =C2=BBMmapAllocator=C2=AB or some std.vm module? --=20 Marco
May 04 2014
prev sibling next sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
On Monday, 28 April 2014 at 16:03:33 UTC, Andrei Alexandrescu 
wrote:
 Fair enough, I'll remove that part of the spec. Thanks! -- 
 Andrei

According to the docs, the "multiple of sizeof(void*)" restriction only applies to posix_memalign (and not to _aligned_malloc and aligned_alloc.) On Monday, 5 May 2014 at 04:04:56 UTC, Andrei Alexandrescu wrote:
 On 5/4/14, 8:06 PM, Marco Leise wrote:
 Virtual memory allocators seem obvious, but there are some
 details to consider.

 1) You should not hard code the allocation granularity in the
    long term. It is fairly easy to get it on Windows and Posix
    systems:

 On Windows:
   SYSTEM_INFO si;
   GetSystemInfo(&si);
   return si.allocationGranularity;

 On Posix:
   return sysconf(_SC_PAGESIZE);

I've decided that runtime-chosen page sizes are too much of a complication for the benefits.

Do the complications arise in the MmapAllocator or the higher level allocators? I'd like to see a Windows allocator based on VirtualAlloc, and afterwards a "SystemAllocator" defined to be MmapAllocator on unix-based and VirtualAlloc based on Windows. This "SystemAllocator" would ideally have an allocationGranularity property.
May 05 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Sun, 04 May 2014 21:05:01 -0700
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 I've decided that runtime-chosen page sizes are too much of a=20
 complication for the benefits.

Alright. Note however, that on Windows the allocation granularity is larger than the page size (64 KiB). So it is a cleaner design in my eyes to use portable wrappers around page size and allocation granularity.
 2) For embedded Linux systems there is the flag
     MAP_UNINITIALIZED to break the guarantee of getting
     zeroed-out memory. So if it is desired, =C2=BBzeroesAllocations=C2=


     could be a writable property there.

This can be easily done, but from what MAP_UNINITIALIZED is strongly=20 discouraged and only implemented on small embedded systems.

Agreed.
 In the cases where I used virtual memory, I often wanted to
 exercise more of its features. As it stands now =C2=BBMmapAllocator=C2=


 works as a basic allocator for 4k blocks of memory. Is that
 the intended scope or are you open to supporting all of it?

For now I just wanted to get a basic mmap-based allocator off the=20 ground. I am aware there's a bunch of things to do. The most prominent=20 is that (according to Jason Evans) Linux is pretty bad at munmap() so=20 it's actually better to advise() pages away upon deallocation but never=20 unmap them. Andrei

That sounds like a more complicated topic than anything I had in mind. I think a =C2=BBstd.virtualmemory=C2=AB module should already implement all the primitives in a portable form, so we don't have to do that again for the next use case. Since cross-platform code is always hard to get right, it could also avoid latent bugs. That module would also offer functionality to get the page size and allocation granularity and wrappers for common needs like getting n KiB of writable memory. Management however (i.e. RAII structs) would not be part of it. It sounds like not too much work with great benefit for a systems programming language. --=20 Marco
May 05 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Sunday, 27 April 2014 at 05:43:07 UTC, Andrei Alexandrescu 
wrote:
 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.


 Andrei

These are my biggest concerns with the allocator API: 1. Struct postblit/destructors don't work reliably, so knowing when to call deallocate() is very difficult. 2. As hard as I try, I still end up with the only references to GC-allocated memory being in my allocator-backed containers. The GC frees all sorts of memory that it shoudn't. It's a giant game af whack-a-mole trying to find the GC memory, which leads me to: 3. GC.removeRange is one of the slowest functions I've ever used. My allocator-backed binary tree implementation took 14 seconds to load a very large data set (compared to RedBlackTree's 35 seconds) and then spent the next five minutes in GC.removeRange before I got bored and killed it.
May 05 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Mon, 05 May 2014 11:23:58 -0700
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 On 5/5/14, 9:57 AM, Marco Leise wrote:
 That sounds like a more complicated topic than anything I had
 in mind. I think a =C2=BBstd.virtualmemory=C2=AB module should already
 implement all the primitives in a portable form, so we don't
 have to do that again for the next use case. Since
 cross-platform code is always hard to get right, it could also
 avoid latent bugs.
 That module would also offer functionality to get the page
 size and allocation granularity and wrappers for common needs
 like getting n KiB of writable memory. Management however
 (i.e. RAII structs) would not be part of it.
 It sounds like not too much work with great benefit for a
 systems programming language.

I think adding portable primitives to=20 http://dlang.org/phobos/std_mmfile.html (plus better yet refactoring its=

 existing code to use them) would be awesome and wouldn't need a DIP. --=20
 Andrei

I like Dmitry's core.vm better, since conceptually we are not necessarily dealing with memory mapped files, but probably with just-in-time compilation, circular buffers, memory access tracing etc. Virtual memory really is a basic building block. --=20 Marco
May 05 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Mon, 05 May 2014 21:13:10 +0400
schrieb Dmitry Olshansky <dmitry.olsh gmail.com>:

 05-May-2014 20:57, Marco Leise =D0=BF=D0=B8=D1=88=D0=B5=D1=82:
 That sounds like a more complicated topic than anything I had
 in mind. I think a =C2=BBstd.virtualmemory=C2=AB module should already
 implement all the primitives in a portable form, so we don't
 have to do that again for the next use case. Since
 cross-platform code is always hard to get right, it could also
 avoid latent bugs.

I had an idea of core.vmm. It didn't survive the last review though,=20 plus I never got around to test OSes aside from Windows & Linux. Comments on initial design are welcome. https://github.com/D-Programming-Language/druntime/pull/653

That's exactly what I had in mind and more. :) These are all free functions that can be used as building blocks for more specific objects. Was there a dedicated review thread on the news group? All I could find was a discussion about why not to use a VMM struct with static functions as a namespace replacement. --=20 Marco
May 05 2014
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Tuesday, 6 May 2014 at 00:30:10 UTC, Brian Schott wrote:
 On Sunday, 27 April 2014 at 05:43:07 UTC, Andrei Alexandrescu 
 wrote:
 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.


 Andrei

These are my biggest concerns with the allocator API: 1. Struct postblit/destructors don't work reliably, so knowing when to call deallocate() is very difficult.

Hmm... destructors have been debated ad nauseam, but what's the problem with postblits?
May 06 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Tue, 06 May 2014 22:55:37 +0400
schrieb Dmitry Olshansky <dmitry.olsh gmail.com>:

 06-May-2014 10:20, Marco Leise =D0=BF=D0=B8=D1=88=D0=B5=D1=82:
 Am Mon, 05 May 2014 21:13:10 +0400
 schrieb Dmitry Olshansky <dmitry.olsh gmail.com>:

 I had an idea of core.vmm. It didn't survive the last review though,
 plus I never got around to test OSes aside from Windows & Linux.
 Comments on initial design are welcome.
 https://github.com/D-Programming-Language/druntime/pull/653

That's exactly what I had in mind and more. :)

Cool. I was ambitious at start until I released that there were about 5-6=20 logically consistent primitives of which many OS-es provided say 3 or 4=20 with little or inexact overlap. That's why I thought of focusing on=20 common recipes, and provide building blocks for them.

These subtle differences between OSs can kill every clean design, hehe. The last time I thought about it I came to the conclusion that some cross-platform APIs are better designed more around use-cases than blindly mapping OS functions. I.g. both chmod() and an opaque integer are bad abstractions for file attributes.
 These are all free functions that can be used as building
 blocks for more specific objects. Was there a dedicated review
 thread on the news group? All I could find was a discussion
 about why not to use a VMM struct with static functions as
 a namespace replacement.

I don't recall such but I think I did a tiny topic on it in general D NG.

You probably mean the same thread: http://forum.dlang.org/thread/l4u68b$30fo$1 digitalmars.com --=20 Marco
May 06 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
Here's an interesting anecdote:

I have a version of DCD that I've been working on for a while 
that uses allocators and an allocator-backed container library. 
(You can find this on Github easily enough, but I'm not 
announcing it yet.)

The allocator version uses 1/3 the memory that the older GC 
version used.
May 06 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 7 May 2014 at 02:48:45 UTC, Brian Schott wrote:
 Here's an interesting anecdote:

 I have a version of DCD that I've been working on for a while 
 that uses allocators and an allocator-backed container library. 
 (You can find this on Github easily enough, but I'm not 
 announcing it yet.)

 The allocator version uses 1/3 the memory that the older GC 
 version used.

What is your feeling on the increased code complexity/fragility, if any?
May 07 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Wednesday, 7 May 2014 at 08:22:51 UTC, John Colvin wrote:
 The allocator version uses 1/3 the memory that the older GC 
 version used.

What is your feeling on the increased code complexity/fragility, if any?

It was difficult because it's very easy to accidentally have references to GC memory that the GC doesn't know about. When the GC starts freeing "live" memory you get all sorts of contract and invariant violations that should never be possible.
May 07 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 7 May 2014 at 09:29:15 UTC, Brian Schott wrote:
 On Wednesday, 7 May 2014 at 08:22:51 UTC, John Colvin wrote:
 The allocator version uses 1/3 the memory that the older GC 
 version used.

What is your feeling on the increased code complexity/fragility, if any?

It was difficult because it's very easy to accidentally have references to GC memory that the GC doesn't know about. When the GC starts freeing "live" memory you get all sorts of contract and invariant violations that should never be possible.

You mean holding references to GC data in a NO_SCAN block?
May 07 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Wednesday, 7 May 2014 at 09:47:44 UTC, John Colvin wrote:
 On Wednesday, 7 May 2014 at 09:29:15 UTC, Brian Schott wrote:
 On Wednesday, 7 May 2014 at 08:22:51 UTC, John Colvin wrote:
 The allocator version uses 1/3 the memory that the older GC 
 version used.

What is your feeling on the increased code complexity/fragility, if any?

It was difficult because it's very easy to accidentally have references to GC memory that the GC doesn't know about. When the GC starts freeing "live" memory you get all sorts of contract and invariant violations that should never be possible.

You mean holding references to GC data in a NO_SCAN block?

I wasn't using GC.malloc, I was using Mallocator from the new std.allocator. There were several tricky cases like a struct that was allocated with malloc containing an array of pointers field. Each element of the array was allocated with malloc, but the array of pointers itself came from a map-filter-array chain somewhere deep inside the code. The GC would free the array while leaving the containing struct corrupted and the elements of the array unreachable.
May 07 2014
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 Added SbrkRegion, SimpleBlocklist, and Blocklist.

An interesting paper, "Reconsidering Custom Memory Allocation - Allen B. Downey": http://www.allendowney.com/ss08/handouts/berger02reconsidering.pdf Bye, bearophile
May 08 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/8/14, 7:02 AM, bearophile wrote:
 Andrei Alexandrescu:

 Added SbrkRegion, SimpleBlocklist, and Blocklist.

An interesting paper, "Reconsidering Custom Memory Allocation - Allen B. Downey": http://www.allendowney.com/ss08/handouts/berger02reconsidering.pdf Bye, bearophile

Yeah, it's a classic (related: http://erdani.com/publications/cuj-2005-12.pdf :o)) but very many things have changed in that space since 2002 - one may say a pendulum swing. Andrei
May 08 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/8/14, 7:24 AM, bearophile wrote:
 Andrei Alexandrescu:

 (related: http://erdani.com/publications/cuj-2005-12.pdf :o))

I have never read this paper. I will read it asap, thank you. After the work on D allocators, and a testing/data collecting phase, perhaps you will have material to write another paper.

Prolly perusing http://erdani.com/d/phobos-prerelease/std_allocator.html is more informative than reading that article. -- Andrei
May 08 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 (related: http://erdani.com/publications/cuj-2005-12.pdf :o))

I have never read this paper. I will read it asap, thank you. After the work on D allocators, and a testing/data collecting phase, perhaps you will have material to write another paper. Bye, bearophile
May 08 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
On Wednesday, 7 May 2014 at 02:48:45 UTC, Brian Schott wrote:
 Here's an interesting anecdote:

 I have a version of DCD that I've been working on for a while 
 that uses allocators and an allocator-backed container library. 
 (You can find this on Github easily enough, but I'm not 
 announcing it yet.)

 The allocator version uses 1/3 the memory that the older GC 
 version used.

This new version of DCD is now checked in at https://github.com/Hackerpilot/DCD.
May 09 2014
prev sibling next sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
On Tuesday, 6 May 2014 at 00:30:10 UTC, Brian Schott wrote:
 These are my biggest concerns with the allocator API:

 [Snip]

 3. GC.removeRange is one of the slowest functions I've ever 
 used. My allocator-backed binary tree implementation took 14 
 seconds to load a very large data set (compared to 
 RedBlackTree's 35 seconds) and then spent the next five minutes 
 in GC.removeRange before I got bored and killed it.

I've just created a PR [1] which changes GC addRange/removeRange to use a treap instead of an unsorted array which you might be interested in testing. It should change your use case of "add N ranges afterwards remove those N ranges" from taking O(N^2) time to O(N log N) time. It would be nice to have a real-world comparison between the enhancement and existing implementation. [1] https://github.com/D-Programming-Language/druntime/pull/788
May 10 2014
prev sibling next sibling parent reply "Brian Schott" <briancschott gmail.com> writes:
On Sunday, 27 April 2014 at 05:43:07 UTC, Andrei Alexandrescu 
wrote:
 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.


 Andrei

Some comments on the version currently checked in (916032a0b6a76b6e37169121ee5cc680bb40b4c4): Line 3173: b2 is unused Line 3177: b3 is unused Line 3496: tids is unused Line 3512: b is unused Line 4235: r2 is never used. This one is probably a bug. Line 5426: b2 is never used Line 5958: b is unused Line 6337: alloc2 is unused. Looks like another bug
May 12 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/12/14, 3:58 PM, Brian Schott wrote:
 On Sunday, 27 April 2014 at 05:43:07 UTC, Andrei Alexandrescu wrote:
 Added SbrkRegion, SimpleBlocklist, and Blocklist.

 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SbrkRegion
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.SimpleBlocklist
 http://erdani.com/d/phobos-prerelease/std_allocator.html#.Blocklist

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

 Destruction is as always welcome. I plan to get into tracing tomorrow
 morning.


 Andrei

Some comments on the version currently checked in (916032a0b6a76b6e37169121ee5cc680bb40b4c4): Line 3173: b2 is unused Line 3177: b3 is unused Line 3496: tids is unused Line 3512: b is unused Line 4235: r2 is never used. This one is probably a bug. Line 5426: b2 is never used Line 5958: b is unused Line 6337: alloc2 is unused. Looks like another bug

Will fix. Awesome, thanks! -- Andrei
May 12 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

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

 Destruction is as always welcome. I plan to get into tracing 
 tomorrow morning.

If you have a system with more cores/CPUs, and each core owns part of the memory (a core can access the memory of another core, but this access is slower than accessing its own memory), can you allocate a memory region specifying what core memory allocate from? (I think Chapel and X10 languages allowed such things from the normal built-in syntax itself). Bye, bearophile
May 18 2014
prev sibling next sibling parent "Brian Schott" <briancschott gmail.com> writes:
I added another static analysis check to dscanner, it pointed out 
this line:

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

Both sides of the && are identical.
Aug 13 2014
prev sibling next sibling parent ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: quoted-printable

On Wed, 13 Aug 2014 21:27:34 +0000
Brian Schott via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 Both sides of the && are identical.

Aug 13 2014
prev sibling parent "Mike" <none none.com> writes:
On Wednesday, 13 August 2014 at 21:27:39 UTC, Brian Schott wrote:
 I added another static analysis check to dscanner, it pointed 
 out this line:

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

 Both sides of the && are identical.

Brian, your work on these tools is awesome. Thanks! Mike
Aug 13 2014