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.





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.





 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
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 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 reply "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
next sibling parent reply "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
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 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 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 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:



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


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


 I just added 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
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/27/14, 9:21 AM, bearophile wrote:

 Andrei Alexandrescu:


 I just added 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 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:



 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 parent reply 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


=20
 I just added MmapAllocator:
=20

=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
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
parent reply 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=




=AB

     could be a writable property there.


=20
 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=




=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?


=20
 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
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 reply 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.


=20
 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
parent reply 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
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. :)


=20
 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.


=20
 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 parent reply 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
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.


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


=20

 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 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?





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.





 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.





 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 reply "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
parent reply 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
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 parent reply "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
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.





 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 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.





 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
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.





 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 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:
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
next sibling parent reply "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
parent reply "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
parent reply "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
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 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 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 reply "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
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 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.





 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.





 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 parent reply "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
next sibling parent ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
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.


it's to REALLY check the flag! ;-)
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