[Issue 2504] Reserve for associative arrays

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=2504

Steven Schveighoffer  changed:

   What|Removed |Added

   See Also||https://issues.dlang.org/sh
   ||ow_bug.cgi?id=17881

--

[Issue 2504] Reserve for associative arrays

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=2504

Iain Buclaw  changed:

   What|Removed |Added

   Priority|P2  |P4

--

[Issue 2504] Reserve for associative arrays

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=2504

greenify  changed:

   What|Removed |Added

 CC||greeen...@gmail.com

--- Comment #7 from greenify  ---
The latest work happened at https://github.com/dlang/druntime/pull/1929

--

[Issue 2504] Reserve for associative arrays

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=2504

Alexandru Razvan Caciulescu  changed:

   What|Removed |Added

 Status|NEW |ASSIGNED
 CC||alexandru.razva...@gmail.co
   ||m
   Assignee|nob...@puremagic.com|alexandru.razva...@gmail.co
   ||m

--

[Issue 2504] Reserve for associative arrays

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=2504

--- Comment #6 from Jon Degenhardt  ---
Discussion and proposal with some general agreement in this forum thread:
https://forum.dlang.org/post/nvbn0a$2tlg$1...@digitalmars.com

--

[Issue 2504] Reserve for associative arrays

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=2504

Jon Degenhardt  changed:

   What|Removed |Added

 CC||jrdemail2000-dl...@yahoo.co
   ||m

--- Comment #5 from Jon Degenhardt  ---
I have noticed meaningful performance degradation after associative arrays
reach about 10 million entries. I gave some GC related numbers in this forum
post: https://forum.dlang.org/post/flxmwyeuhjcuekfed...@forum.dlang.org

In addition to GC stats, it appears likely that resizing the underlying array
will be costly at these numbers. Having an ability to reserve capacity for a
minimum number of keys may address this.

--

[Issue 2504] Reserve for associative arrays

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=2504


Michael Rynn y0uf00...@gmail.com changed:

   What|Removed |Added

 CC||y0uf00...@gmail.com


--- Comment #4 from Michael Rynn y0uf00...@gmail.com 2010-04-17 04:50:13 PDT 
---
See enhancement 4098.
I have experimented with a NodeHeap for the AA, that allocates Nodes in much
bigger blocks, and this does speed by up a considerable amount the insertion
and cleanup times. The NodeHeap idea is a single sized block dedicated heap
manager created for each AA instance.

No advantage at all for lookup times.

The disadvantage is that Nodes released by a remove, are not returned to the GC
pool until the entire block of Nodes has been removed. Of course when it does
get freed, its in a big blocks at once. Also when allocating Nodes one after
the other, I suppose a smart memory heap might be carving up much bigger blocks
anyway, with various Pools for different object sizes.  

Having a manual AA.clear helps the GC as well. 

Even so, having a node heap and using for the first time, the system must get a
new big bunch of memory, and maybe that will always take some time.

Its not in the current 4098 set (which is a lot to swallow already), but I it
could be an optional run time extra parameter to the HashMap/HashSet setup
wrapper. It uses lots of really small nodes.

The AA management object would then have a non-null heap manager object, to
allocate and free blocks from a dedicated instance pool (Just like the Tango
HashMap, which does exactly this).

I have already proposed to add some more fields to the hash map management
object, and one more non-default runtime option (only available from HashMap
template wrapper) will hopefully not be a heap of trouble.

If it was an option, would people use it wisely?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 2504] Reserve for associative arrays

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=2504



--- Comment #3 from ZY Zhou rin...@gmail.com 2009-11-30 21:24:04 PST ---
(In reply to comment #2)
 No, this is because, on the second run, the program has already reserved a
 bunch of memory from the OS, so the GC doesn't run as often.

try this:

import std.stdio;
void main(){
 int[int] a;
 foreach(i;0..20_000_000){
  a[i] = i;
  if((i0x) == 0) writeln(i);
 }
}

You can see how slow it becomes when AA is large.
I don't think memory allocation could take so much time.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 2504] Reserve for associative arrays

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=2504


ZY Zhou rin...@gmail.com changed:

   What|Removed |Added

 CC||rin...@gmail.com


--- Comment #1 from ZY Zhou rin...@gmail.com 2009-09-23 01:38:43 PDT ---
(In reply to comment #0)
 It appears that adding an element to an associative array always triggers a
 memory allocation.  Especially in multithreaded code, this is inefficient.  It
 would be nice if associative arrays had a .reserve(size_t n) property, which
 reserved enough space for n objects, and stored the capacity internally.  The
 idea is that, until the reserve buffer is exhausted, no interaction of any 
 kind
 with the GC would be needed to add an element to the AA.

It's not all about memory

int[int] a;
foreach(i;0..20_000_000) a[i] = i; //takes 2 _minutes_
foreach(i;0..20_000_000) a[i] = i; //do it again, only 2 seconds

60 times slower.
If it's memory allocation problem, the result should be similar to Dynamic
array:

int[] t;
foreach(i;0..20_000_000) t ~= i; // 2 seconds
foreach(i;0..20_000_000) t[i] = i; // 0.3 seconds

I guess AA rehashs the whole array when capacity changes, and rehashing is much
slower than memory allocation.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---