www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is D associative array thread safe, and will it relocate memory

reply raojm <raojm 91ne.com> writes:
Is D associative array  thread safe, and  will it relocate memory when
add or delete a value?

Where I can find the implemention.
Dec 06 2011
next sibling parent Jacob Carlborg <doob me.com> writes:
On 2011-12-07 08:59, raojm wrote:

 Is D associative array  thread safe, and  will it relocate memory when
 add or delete a value?
 
 Where I can find the implemention.


You should be able to find the implementation somewhere in druntime:

https://github.com/D-Programming-Language/druntime

-- 
/Jacob Carlborg
Dec 07 2011
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 07 Dec 2011 08:59:32 +0100, raojm <raojm 91ne.com> wrote:


 Is D associative array  thread safe, and  will it relocate memory when
 add or delete a value?

 Where I can find the implemention.


No it's not, and yes it has to relocate memory.
It's working as a hashtable not a binary tree, so all
pointers will be invalidated by adding/removing.
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d
Dec 07 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:

 On Wed, 07 Dec 2011 08:59:32 +0100, raojm <raojm 91ne.com> wrote:

 Is D associative array  thread safe, and  will it relocate memory when
 add or delete a value?
 
 Where I can find the implemention.


 
 No it's not, and yes it has to relocate memory.
 It's working as a hashtable not a binary tree, so all
 pointers will be invalidated by adding/removing.
 https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d


Yeah. AFAIK, it's impossible to have a hash table which doesn't risk 
reallocating something when adding a value to it, unless you limit how many 
elements it can hold or somesuch, which would make it considerably less 
useful. Typically, when a hash table gets full enough, it rehashes itself, 
which definitely involves allocating more memory, and possible reallocating a 
large portion of what it's already allocated. So, there's no way that an AA 
can avoid the risk of reallocating when elements are added to it, pretty much 
regardless of its implementation. It's an attribute of the data structure.

But since adding to a hash table obviously isn't going to be atomic, there's 
no way that it's going to be thread-safe regardless. It would have to have to 
be using a mutex internally or be synchronized, and there's no way that the 
built-in AA is going to do that. It would harm efficiency in the general case 
for a special case. If you're using a shared AA and want to ensure thread-
safety, you're going to have to use mutexes or synchronized blocks or whatnot 
to ensure that only one thread is using it at a time.

- Jonathan M Davis
Dec 07 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 07 Dec 2011 04:00:34 -0500, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:

 On Wed, 07 Dec 2011 08:59:32 +0100, raojm <raojm 91ne.com> wrote:

 Is D associative array  thread safe, and  will it relocate memory when
 add or delete a value?

 Where I can find the implemention.


 No it's not, and yes it has to relocate memory.
 It's working as a hashtable not a binary tree, so all
 pointers will be invalidated by adding/removing.
 https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d


 Yeah. AFAIK, it's impossible to have a hash table which doesn't risk
 reallocating something when adding a value to it, unless you limit how  
 many
 elements it can hold or somesuch, which would make it considerably less
 useful. Typically, when a hash table gets full enough, it rehashes  
 itself,
 which definitely involves allocating more memory, and possible  
 reallocating a
 large portion of what it's already allocated. So, there's no way that an  
 AA
 can avoid the risk of reallocating when elements are added to it, pretty  
 much
 regardless of its implementation. It's an attribute of the data  
 structure.


dcollections' HashMap does not invalidate cursors when adding data, even  
when a rehash is done.  The rehash routine specifically is written to make  
this possible.

However, it does invalidate ranges.

Note that for any hash implementation, the only thing that needs to be  
reallocated is the bucket array.  In many implementations, this is not  
where the data is stored.

-Steve
Dec 07 2011
parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 07 Dec 2011 14:51:49 +0100, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Wed, 07 Dec 2011 04:00:34 -0500, Jonathan M Davis  
 <jmdavisProg gmx.com> wrote:


 On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:

 On Wed, 07 Dec 2011 08:59:32 +0100, raojm <raojm 91ne.com> wrote:

 Is D associative array  thread safe, and  will it relocate memory  


 when

 add or delete a value?

 Where I can find the implemention.


 No it's not, and yes it has to relocate memory.
 It's working as a hashtable not a binary tree, so all
 pointers will be invalidated by adding/removing.
 https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d






On a second thought that was wrong, D's AA do allocate one node per value,
so pointers to the values won't get invalidated. But simple optimizations
as adding a freelist would break this.
Depending on your application you should either lock access or
have a look at implementing a lock-free map.


 Yeah. AFAIK, it's impossible to have a hash table which doesn't risk
 reallocating something when adding a value to it, unless you limit how  
 many
 elements it can hold or somesuch, which would make it considerably less
 useful. Typically, when a hash table gets full enough, it rehashes  
 itself,
 which definitely involves allocating more memory, and possible  
 reallocating a
 large portion of what it's already allocated. So, there's no way that  
 an AA
 can avoid the risk of reallocating when elements are added to it,  
 pretty much
 regardless of its implementation. It's an attribute of the data  
 structure.


 dcollections' HashMap does not invalidate cursors when adding data, even  
 when a rehash is done.  The rehash routine specifically is written to  
 make this possible.

 However, it does invalidate ranges.

 Note that for any hash implementation, the only thing that needs to be  
 reallocated is the bucket array.  In many implementations, this is not  
 where the data is stored.

 -Steve
Dec 07 2011