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

 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



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