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.

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?

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.

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?

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?

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?

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

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

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.

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