LinearProbeHashtable

classic Classic list List threaded Threaded
33 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable / Remove second volatile read?

Jens Wilke
On Wednesday 01 June 2016 16:08:08 Peter Levart wrote:
> You see, volatile read of table in GetThread might be performed before
> the volatile write of table in PutThread.

Thanks for detailed write up, I see my mistake!

That's a very important detail for a general hash table.

For hashing class instances you do not need equals at all. ;)

Cheers,

Jens

--
"Everything superfluous is wrong!"

   // Jens Wilke - headissue GmbH - Germany
 \//  https://headissue.com
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Nathan and Ila Reynolds
In reply to this post by Michael Kuhlmann
> First filling the map, then removing most of the elements and never add many again? I've never seen that.

I have.  Consider the following 2 data points.

Large Sparse Collections are collections with the following property: 2 * size ≤ capacity && capacity > default.  This means that the collection had enough elements to cause the capacity to grow beyond the default and then a lot of elements were removed.  0.8% of the bytes of an average Java heap is consumed with Large Sparse collections.  0.4% of the bytes of an average Java heap is consumed with Large Sparse HashMaps.  0.1% of the bytes of an average Java heap is consumed with Large Sparse ConcurrentHashMaps.

Empty Used Collections are collections that contained at least 1 element at some point in time but are empty at the time of the heap dump.  0.3% of an average Java heap is filled with Empty Used Collections split evenly among ArrayLists, HashMaps and ConcurrentHashMaps.

With only 0.8% and 0.3% of an average heap wasted, it probably isn't worth the human effort or CPU time to handle these cases.  However, these cases do exist.

-Nathan

-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Kuhlmann
Sent: Wednesday, June 01, 2016 2:11 AM
To: [hidden email]
Subject: Re: [concurrency-interest] LinearProbeHashtable

Am 01.06.2016 um 10:35 schrieb Peter Levart:
> But, as said, it may
> be beneficial to trigger rehashing (with expunging of tombstones and
> possible shrinking) also in remove() in order to more eagerly optimize
> lookup time by preventing building-up future "clusters".

I wouldn't do it. You risk a "pumping effect" when many elements are added and removed frequently.

What would be the use case? First filling the map, then removing most of the elements and never add many again? I've never seen that.

And it's even more unlikely in ClassValue where removals will definitely be the exception.

HashMap doesn't shrink either for good reasons.

-Michael


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Nitin chaudhary
Hi Concurrency Experts,

It might be a stupid question but I am unable to understand the behaviour of join Method.

Attached two program 1 program 'JoinExample' in line number 24, calling  join on thread t and waits until thread t finishes. Program finishes well.

But in Example Second 'NoVisibility' Line number 13, my Reader thread got stuck and it seems like halt for ever. It should call a loop second time but it did not. If possible kindly do let me know the reason.

Thank you in advance and pardon my English.

Regards,
Nitin Kumar
#:+91 9654151525


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

JoinExample.java (952 bytes) Download Attachment
NoVisibility.java (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: i wait for myself to die

Remi Forax
Hi Nitin,
i'm not really an expert by
  Thread.currentThread().join()
means that you stop the current thread until the current thread finish the method run(),
hence the wait forever.

cheers,
Rémi


De: "Nitin chaudhary" <[hidden email]>
À: [hidden email]
Envoyé: Samedi 4 Juin 2016 00:46:14
Objet: Re: [concurrency-interest] LinearProbeHashtable

Hi Concurrency Experts,

It might be a stupid question but I am unable to understand the behaviour of join Method.

Attached two program 1 program 'JoinExample' in line number 24, calling  join on thread t and waits until thread t finishes. Program finishes well.

But in Example Second 'NoVisibility' Line number 13, my Reader thread got stuck and it seems like halt for ever. It should call a loop second time but it did not. If possible kindly do let me know the reason.

Thank you in advance and pardon my English.

Regards,
Nitin Kumar
#:+91 9654151525


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Roman Elizarov
In reply to this post by Peter Levart

> I wish I could find a way to reuse the slot occupied by a tombstone.
> Keep in mind that get() must be lock-free. For that to work, I would need an atomic read from two consecutive array slots. Otherwise I could read a key belonging to one mapping > and until I get to read the value slot, it will contain the value from another mapping. This phenomena could be called "Entry tearing".

The irony is that it is possible (at least on x86 hardware) in very efficient way, yet Java does not provide a way for us to do so.

Below, I believe, is the exhaustive classification of ways to reuse tomstones in a concurrent key-value hashmap (key and value are separated) with wait-free/lock-free reads:

1. Use double-word reads to read both  key and value and double-word CAS to update them at the same time. You can do it on x86, but not via existing or future (Java 9) Java APIs. It is the most efficient approach (both memory and CPU time). I wonder if we can hope to get this available via VarHandles in Java 10 (when we can define a value type with a pair of references).

2. Introduce Entry object to combine key & value into a single object. It is still pretty fast, but it considerably (a factor of many times) increases hashmap's memory consumption and decreases data structure memory locality (an extra memory dereference to wait for memory load on).

3. Coordinate reads and write, e.g. allow your reads to modify hashtable to signal that the read it in process. There are a lots of actual implementation approaches (see Harris's works for CASN, for example, may STMs will do the trick, too). It "solves" the problem even when all you have is a single-reference CAS. You still keep low memory consumption for your data, but it adds a lot of overhead to read and write operations. IMHO, it has practical use only if you have huge amount of data (some kind of in-memory database) which you read/write not that often.






_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Roman Elizarov
In reply to this post by Peter Levart
There's actually another approach that might do the trick. Just combine key and value into a StampedLock, e.g. add an int version to each key/value pair (you'll have to do it in a separate int array until we have project Valhalla value types in Java) This way you can do lock-free consistent reads of key/value pairs (by detecting entry tearing just like StampedLock does). It only adds 4 bytes per key/value pair (much less than a separate Entry object) and enables tomstones reuse.

-----Original Message-----
From: Roman Elizarov
Sent: Monday, June 6, 2016 12:57 PM
To: 'Peter Levart' <[hidden email]>; Michael Kuhlmann <[hidden email]>; [hidden email]
Subject: RE: [concurrency-interest] LinearProbeHashtable


> I wish I could find a way to reuse the slot occupied by a tombstone.
> Keep in mind that get() must be lock-free. For that to work, I would need an atomic read from two consecutive array slots. Otherwise I could read a key belonging to one mapping > and until I get to read the value slot, it will contain the value from another mapping. This phenomena could be called "Entry tearing".

The irony is that it is possible (at least on x86 hardware) in very efficient way, yet Java does not provide a way for us to do so.

Below, I believe, is the exhaustive classification of ways to reuse tomstones in a concurrent key-value hashmap (key and value are separated) with wait-free/lock-free reads:

1. Use double-word reads to read both  key and value and double-word CAS to update them at the same time. You can do it on x86, but not via existing or future (Java 9) Java APIs. It is the most efficient approach (both memory and CPU time). I wonder if we can hope to get this available via VarHandles in Java 10 (when we can define a value type with a pair of references).

2. Introduce Entry object to combine key & value into a single object. It is still pretty fast, but it considerably (a factor of many times) increases hashmap's memory consumption and decreases data structure memory locality (an extra memory dereference to wait for memory load on).

3. Coordinate reads and write, e.g. allow your reads to modify hashtable to signal that the read it in process. There are a lots of actual implementation approaches (see Harris's works for CASN, for example, may STMs will do the trick, too). It "solves" the problem even when all you have is a single-reference CAS. You still keep low memory consumption for your data, but it adds a lot of overhead to read and write operations. IMHO, it has practical use only if you have huge amount of data (some kind of in-memory database) which you read/write not that often.






_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Michael Kuhlmann
In reply to this post by Roman Elizarov
Am 06.06.2016 um 12:56 schrieb Roman Elizarov:
>
> 1. Use double-word reads to read both  key and value and double-word CAS to update them at the same time. You can do it on x86, but not via existing or future (Java 9) Java APIs. It is the most efficient approach (both memory and CPU time). I wonder if we can hope to get this available via VarHandles in Java 10 (when we can define a value type with a pair of references).

This would only work if the object reference is only 32 bit long, which
is not necessarily the case. (Imagine VMs with more than 32 gb heap.)

So it will never be supported by Java language features.

-Michael

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Roman Elizarov
x86-64 has CMPXCHG16B instruction that can work with two 64-bit references at the same time.

-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Kuhlmann
Sent: Monday, June 6, 2016 2:12 PM
To: [hidden email]
Subject: Re: [concurrency-interest] LinearProbeHashtable

Am 06.06.2016 um 12:56 schrieb Roman Elizarov:
>
> 1. Use double-word reads to read both  key and value and double-word CAS to update them at the same time. You can do it on x86, but not via existing or future (Java 9) Java APIs. It is the most efficient approach (both memory and CPU time). I wonder if we can hope to get this available via VarHandles in Java 10 (when we can define a value type with a pair of references).

This would only work if the object reference is only 32 bit long, which is not necessarily the case. (Imagine VMs with more than 32 gb heap.)

So it will never be supported by Java language features.

-Michael

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Michael Kuhlmann
Am 06.06.2016 um 14:51 schrieb Roman Elizarov:
> x86-64 has CMPXCHG16B instruction that can work with two 64-bit references at the same time.
>

Ah, I didn't know this. Thanks!

But then, again, there is the problem how to support other CPU types,
including 32-Bit X84.

-Michael

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Viktor Klang

The downgrade route would fall back to critical sections?

--
Cheers,

On Jun 6, 2016 3:03 PM, "Michael Kuhlmann" <[hidden email]> wrote:
Am 06.06.2016 um 14:51 schrieb Roman Elizarov:
> x86-64 has CMPXCHG16B instruction that can work with two 64-bit references at the same time.
>

Ah, I didn't know this. Thanks!

But then, again, there is the problem how to support other CPU types,
including 32-Bit X84.

-Michael

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Roman Elizarov
In reply to this post by Michael Kuhlmann
32-bit x86 has CMPXCHG8B.

However, there could be an architecture that does not support this kind of instructions natively. Even reading two references atomically (yet alone CASing them) can be a problem on some (what?) architectures. However, some kind of fallback can always be found and implemented, just like it now happens with "volatile" 64 bit variables that are required to be atomic, but not all architectures support them.

Critical section is always the last-resort fallback that JVM can implement in such cases, but you do much better than that. Since you are going to implement those fallbacks in C++ code (in assembly, actually), you can use CASN-like approach of Harris, for example, which gives you both lock-freedom and disjoint-access-parallelism.

/Roman

-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Kuhlmann
Sent: Monday, June 6, 2016 2:59 PM
To: [hidden email]
Subject: Re: [concurrency-interest] LinearProbeHashtable

Am 06.06.2016 um 14:51 schrieb Roman Elizarov:
> x86-64 has CMPXCHG16B instruction that can work with two 64-bit references at the same time.
>

Ah, I didn't know this. Thanks!

But then, again, there is the problem how to support other CPU types, including 32-Bit X84.

-Michael

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Alex Otenko
In reply to this post by Roman Elizarov
But does it have a way to surface in Java? (Direct)ByteBuffers?..

Alex

> On 6 Jun 2016, at 13:51, Roman Elizarov <[hidden email]> wrote:
>
> x86-64 has CMPXCHG16B instruction that can work with two 64-bit references at the same time.
>
> -----Original Message-----
> From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Kuhlmann
> Sent: Monday, June 6, 2016 2:12 PM
> To: [hidden email]
> Subject: Re: [concurrency-interest] LinearProbeHashtable
>
> Am 06.06.2016 um 12:56 schrieb Roman Elizarov:
>>
>> 1. Use double-word reads to read both  key and value and double-word CAS to update them at the same time. You can do it on x86, but not via existing or future (Java 9) Java APIs. It is the most efficient approach (both memory and CPU time). I wonder if we can hope to get this available via VarHandles in Java 10 (when we can define a value type with a pair of references).
>
> This would only work if the object reference is only 32 bit long, which is not necessarily the case. (Imagine VMs with more than 32 gb heap.)
>
> So it will never be supported by Java language features.
>
> -Michael
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable

Roman Elizarov
Project Valhalla? E.g., define a value class with key and value references, use array of these value class in your hashmap implementation. Use VarHandle to volatile (atomically) read it and CAS it. Assuming that project Valhalla implementation uses platform-specific instructions when they are available, then it is all going to work as fast as the corresponding C/C++ code.

-----Original Message-----
From: Alex Otenko [mailto:[hidden email]]
Sent: Wednesday, June 8, 2016 12:30 PM
To: Roman Elizarov <[hidden email]>
Cc: Michael Kuhlmann <[hidden email]>; [hidden email]
Subject: Re: [concurrency-interest] LinearProbeHashtable

But does it have a way to surface in Java? (Direct)ByteBuffers?..

Alex

> On 6 Jun 2016, at 13:51, Roman Elizarov <[hidden email]> wrote:
>
> x86-64 has CMPXCHG16B instruction that can work with two 64-bit references at the same time.
>
> -----Original Message-----
> From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Kuhlmann
> Sent: Monday, June 6, 2016 2:12 PM
> To: [hidden email]
> Subject: Re: [concurrency-interest] LinearProbeHashtable
>
> Am 06.06.2016 um 12:56 schrieb Roman Elizarov:
>>
>> 1. Use double-word reads to read both  key and value and double-word CAS to update them at the same time. You can do it on x86, but not via existing or future (Java 9) Java APIs. It is the most efficient approach (both memory and CPU time). I wonder if we can hope to get this available via VarHandles in Java 10 (when we can define a value type with a pair of references).
>
> This would only work if the object reference is only 32 bit long, which is not necessarily the case. (Imagine VMs with more than 32 gb heap.)
>
> So it will never be supported by Java language features.
>
> -Michael
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
12