Thread overview | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
September 17, 2014 GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Have anybody cooked any GC-less variants of hash-tables (associative arrays) that take keys and values with value semantics only. Similar to how X[] relates to std.containers.Array!X I need this to index my nodes in graphs with tens of millions of nodes. |
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Wednesday, 17 September 2014 at 10:39:07 UTC, Nordlöw wrote:
> Have anybody cooked any GC-less variants of hash-tables (associative arrays) that take keys and values with value semantics only.
Important follow-up question: If types of key and value all have value semantics (no indirections) will the hash-table still use the GC for allocations?
|
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Wed, 17 Sep 2014 10:39:05 +0000, Nordlöw wrote: > Have anybody cooked any GC-less variants of hash-tables (associative arrays) that take keys and values with value semantics only. > > Similar to how > > X[] > > relates to > > std.containers.Array!X > > I need this to index my nodes in graphs with tens of millions of nodes. See our hashmap and hashset implementations here: https://github.com/economicmodeling/containers/tree/master/src/containers These containers are all certified GC-free. |
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Justin Whear | On Wednesday, 17 September 2014 at 15:27:40 UTC, Justin Whear wrote:
> These containers are all certified GC-free.
Superb!
One question though:
AFAIK a builtin hash-table in D shouldn't require nor use any GC-allocations if the keys and values all have reference semantics right (no string class, nor member indirections)? What is the current status on this in dmd/druntime?
|
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Justin Whear | On Wednesday, 17 September 2014 at 15:27:40 UTC, Justin Whear wrote:
> These containers are all certified GC-free.
What's the difference between std.containers.Array and DynamicArray? The RC?
|
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Wednesday, 17 September 2014 at 19:39:16 UTC, Nordlöw wrote:
> On Wednesday, 17 September 2014 at 15:27:40 UTC, Justin Whear wrote:
>> These containers are all certified GC-free.
What'a the cost of using hashset in favour of hashmap if I want the to use the
Range range()
property?
|
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Wed, Sep 17, 2014 at 07:23:01PM +0000, "Nordlöw" via Digitalmars-d-learn wrote: > On Wednesday, 17 September 2014 at 15:27:40 UTC, Justin Whear wrote: > >These containers are all certified GC-free. > > Superb! > > One question though: > > AFAIK a builtin hash-table in D shouldn't require nor use any GC-allocations if the keys and values all have reference semantics right (no string class, nor member indirections)? What is the current status on this in dmd/druntime? How do you implement a completely GC-free AA with no limit on number of entries stored? I mean, where would it get the memory to store the hashtable from? T -- Once bitten, twice cry... |
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | H. S. Teoh:
> How do you implement a completely GC-free AA with no limit on number of entries stored?
Ada2012 has a fixed-size hash in the standard library, it can even be allocated on the stack. But the number of entries is not unlimited.
Bye,
bearophile
|
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | On Wednesday, 17 September 2014 at 19:51:06 UTC, H. S. Teoh via Digitalmars-d-learn wrote:
> How do you implement a completely GC-free AA with no limit on number of
> entries stored? I mean, where would it get the memory to store the
> hashtable from?
I mean, GC-free not heap-free. An AA of course needs dynamic memory management a la C++'s std::vector.
|
September 17, 2014 Re: GC-less Hash-Tables (AA) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Wed, Sep 17, 2014 at 10:26:16PM +0000, "Nordlöw" via Digitalmars-d-learn wrote: > On Wednesday, 17 September 2014 at 19:51:06 UTC, H. S. Teoh via Digitalmars-d-learn wrote: > >How do you implement a completely GC-free AA with no limit on number of entries stored? I mean, where would it get the memory to store the hashtable from? > > I mean, GC-free not heap-free. An AA of course needs dynamic memory management a la C++'s std::vector. So you would use malloc/free? T -- It is of the new things that men tire --- of fashions and proposals and improvements and change. It is the old things that startle and intoxicate. It is the old things that are young. -- G.K. Chesterton |
Copyright © 1999-2021 by the D Language Foundation