LinearProbeHashtable

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

LinearProbeHashtable

Peter Levart
Hi concurrency experts,

As part of an attempt to optimize the ClassValue API for small number of
elements per Class in OpenJDK, I came up with a proposal to leverage
ConcurrentHashMap, which improves the footprint overhead considerably
(has ~ 1/2 footprint overhead of current ClassValue), simplifies
ClassValue implementation and is only barely slower with lookups than
existing ClassValue implementation. Here's the code if anyone is
interested to see it:

http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.02/

But a lookup slowdown of about 10-15 % is not acceptable, they say. So I
created a simple specialized map-like construct to replace CHM in this
ClassValue implementation - LinearProbeHashtable which improves lookup
performance. As there was interest to use it elsewhere in the inner
workings of JDK infrastructure, namely in MethodType interning support,
to be able to use VarHandles for implementation of CHM without fear of
circular dependencies, I though of presenting the code of
LinearProbeHashtable on this list in hope that someone could spot any
obvious issues with it:

http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.04.2/src/java.base/share/classes/java/lang/LinearProbeHashtable.java.html

This is not a general-purpose Map implementation. It does not even
implement the Map interface. The methods it has in common with Map
interface should adhere to Map's specification though. The purpose of
this implementation is:

- quick lock-free lookups
- compact footprint
- resonable for modifications

To be used in situations that are mostly lookup-based such as interning,
caching, etc. Where the number of entries is not large and keys already
implement good hash code(s) for power-of-2 length table(s).

So, do you see any issues with this implementation?

Regards, Peter

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

Re: LinearProbeHashtable

Jens Wilke
Peter,

thanks for sharing this. It's a nice afternoon read :)

On Tuesday 31 May 2016 12:44:09 Peter Levart wrote:
> So, do you see any issues with this implementation?

I have a "non concurrency" related remark. It took me quite a while, to see whether the table
gets expanded when tombstones get to much. It does, probably. Maybe the code can be more
readable here? E.g.:

         if (2 * capacity(inserted + 1) > curLen) {
            int newLen = 2 * capacity((inserted - tombstoned) * 3 / 2 + 1);

The numbers 2 and 3 repeat at other places, too, probably you mean always the same... When implementing hash tables,
I personally always like to have the load factor as parameter to use it in unit tests (and benchmarks!).

> - quick lock-free lookups

This only holds, if you don't have too much tombstones around. Right now, your worst case lookup speed will be much worse then
CHM. From the use case you describe probably its expected to have not much removals and updates. I would limit the number
of tombstones and rehash if it is reached to have a better worst case scenario guarantee.

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

Peter Levart
Hi Jens,

Thanks for taking a look. I'm happy to answer your comments...

On 05/31/2016 04:53 PM, Jens Wilke wrote:

> Peter,
>
> thanks for sharing this. It's a nice afternoon read :)
>
> On Tuesday 31 May 2016 12:44:09 Peter Levart wrote:
>> So, do you see any issues with this implementation?
> I have a "non concurrency" related remark. It took me quite a while, to see whether the table
> gets expanded when tombstones get to much. It does, probably. Maybe the code can be more
> readable here? E.g.:
>
>           if (2 * capacity(inserted + 1) > curLen) {
>              int newLen = 2 * capacity((inserted - tombstoned) * 3 / 2 + 1);

A tombstone is just a deleted entry (well a key, its corresponding value
is cleared) - it occupies the slot. 'inserted' is used to track the
number of entries in the table (including tombstones) and the table is
rehashed (possibly resized too) when the load is about to grow beyond 2/3.
>
> The numbers 2 and 3 repeat at other places, too, probably you mean always the same... When implementing hash tables,
> I personally always like to have the load factor as parameter to use it in unit tests (and benchmarks!).

The only place where load factor is coded is in the capacity() method.
The '2' in if (2 * capacity(inserted + 1) > curLen) above is to convert
from capacity to table length (as two table slots are used for each
key/value pair in the table). The 3/2 factor in the next line is just
coincidentally equal to 1/loadFactor and has nothing to do with it. It
is used as a kind of "hysteresis loop" that prevents oscillating around
the tipping point (the point where capacity() function jumps by a factor
of 2). The table is rehashed when, as mentioned, the number of inserted
entries (including tombstoned entries) grows over loadFactor * capacity.
Rehashing also gets rid of tombstones.

Imagine a table that contains just one tombstone when it is rehashed. if
the new table length was computed simply as newLen = 2 *
capacity(inserted - tombstoned + 1), the new table would have the same
length as the old one and we would end up with new rehashed table with
space for a single entry before another rehashing was necessary. The 3/2
factor in newLen = 2 * capacity((inserted - tombstoned) * 3 / 2 + 1)
guarantees that rehashing is not needed for at least another size()/2 +
1 insertions. When this factor is 1 <= factor < 2, it does not affect
normal growth when entries are just inserted and never removed.

>
>> - quick lock-free lookups
> This only holds, if you don't have too much tombstones around. Right now, your worst case lookup speed will be much worse then
> CHM. From the use case you describe probably its expected to have not much removals and updates. I would limit the number
> of tombstones and rehash if it is reached to have a better worst case scenario guarantee.

Tombstones don't worsen lookup speed compared to a table state before
removing an entry that became a tombstone. They can actually improve
lookup speed compared to a pre-remove state as they contain this 'skip'
int field that tells how many slots to jump to get over the whole run of
consecutive tombstones in one go. Planting the tombstone does not
improve lookup as much as removing an entry right away would, of course.
They are a necessary evil to enable lock-free lookups.

But your idea is a good one, thanks. Why would only insertions trigger
rehashing. Removals could do that too. I'll think about the strategy...

Note: "load" in above sentences pertains to occupancy of the hash table
- not the CPU.

>
> Cheers,
>
> Jens
>

Regards, Peter

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

Re: LinearProbeHashtable

Jens Wilke
On Tuesday 31 May 2016 18:50:53 Peter Levart wrote:

> The only place where load factor is coded is in the capacity() method.
> The '2' in if (2 * capacity(inserted + 1) > curLen) above is to convert
> from capacity to table length (as two table slots are used for each
> key/value pair in the table). The 3/2 factor in the next line is just
> coincidentally equal to 1/loadFactor and has nothing to do with it. It
> is used as a kind of "hysteresis loop" that prevents oscillating around
> the tipping point (the point where capacity() function jumps by a factor
> of 2). The table is rehashed when, as mentioned, the number of inserted
> entries (including tombstoned entries) grows over loadFactor * capacity.
> Rehashing also gets rid of tombstones.
>
> Imagine a table that contains just one tombstone when it is rehashed. if
> the new table length was computed simply as newLen = 2 *
> capacity(inserted - tombstoned + 1), the new table would have the same
> length as the old one and we would end up with new rehashed table with
> space for a single entry before another rehashing was necessary. The 3/2
> factor in newLen = 2 * capacity((inserted - tombstoned) * 3 / 2 + 1)
> guarantees that rehashing is not needed for at least another size()/2 +
> 1 insertions. When this factor is 1 <= factor < 2, it does not affect
> normal growth when entries are just inserted and never removed.

Exactly, that is the strange thing. But, usually the load factor only determines _when_
to extend, you do not need it to calculate the next size. The next expansion
size is all the time  tab.length * 2, since your size is a power of two, and you
do not insert more then one element at a time, so that there is a need to expand more.

The load factor is a "magic number". It is inside expand(), in checkSize() and in capacity().

I don't see a real need for the methods checkSize() and capacity() in that form. At least
for the current functionality without shrink support. Just an idea how this could look
more obvious (hopefully...):

static final int SLOTS_PER_ENTRY = 2;
static final int LOAD_PERCENT = 66;
. . .
int maximumCapacity = tab.length / SLOTS_PER_ENTRY * LOAD_PERCENT / 100;
if (inserted > maximumCapactiy) {
  // needs expansion or tombstone cleanup!
  int newLen = tab.length;
  if (size() > maximumCapacity) {
    // needs expansion!
    newLen = tab.length * 2;
    if (newLen < 0) { throw new OutOfMemoryException("...."); }
  }
  Object[] newTab = new Object[newLen];
  // do the rehash
}

Interestingly your current code would also shrink the table, since
you calculate the next table length based on the real size. But its in the put() path :)

BTW:

   public int size() {
     synchronized (lock) {
       return inserted - tombstoned;
     }
   }

Why not have the size as variable, and calculate occupation = size + tombstone for the internal
purposes?

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

Peter Levart
Hi Jens,


On 05/31/2016 08:48 PM, Jens Wilke wrote:

> On Tuesday 31 May 2016 18:50:53 Peter Levart wrote:
>
>> The only place where load factor is coded is in the capacity() method.
>> The '2' in if (2 * capacity(inserted + 1) > curLen) above is to convert
>> from capacity to table length (as two table slots are used for each
>> key/value pair in the table). The 3/2 factor in the next line is just
>> coincidentally equal to 1/loadFactor and has nothing to do with it. It
>> is used as a kind of "hysteresis loop" that prevents oscillating around
>> the tipping point (the point where capacity() function jumps by a factor
>> of 2). The table is rehashed when, as mentioned, the number of inserted
>> entries (including tombstoned entries) grows over loadFactor * capacity.
>> Rehashing also gets rid of tombstones.
>>
>> Imagine a table that contains just one tombstone when it is rehashed. if
>> the new table length was computed simply as newLen = 2 *
>> capacity(inserted - tombstoned + 1), the new table would have the same
>> length as the old one and we would end up with new rehashed table with
>> space for a single entry before another rehashing was necessary. The 3/2
>> factor in newLen = 2 * capacity((inserted - tombstoned) * 3 / 2 + 1)
>> guarantees that rehashing is not needed for at least another size()/2 +
>> 1 insertions. When this factor is 1 <= factor < 2, it does not affect
>> normal growth when entries are just inserted and never removed.
> Exactly, that is the strange thing. But, usually the load factor only determines _when_
> to extend, you do not need it to calculate the next size. The next expansion
> size is all the time  tab.length * 2, since your size is a power of two, and you
> do not insert more then one element at a time, so that there is a need to expand more.
>
> The load factor is a "magic number". It is inside expand(), in checkSize() and in capacity().

Just in checkSize() and capacity() - not in rehash(). It is hardcoded
because of the specific nature of linear-probe hashtable that is very
sensitive on its value. values larger than 2/3 are not sensible as
"clustering" effects explode and values much lower than 2/3 make the
table occupy to much space.

>
> I don't see a real need for the methods checkSize() and capacity() in that form. At least
> for the current functionality without shrink support.

There is shrink support in current functionality (see below).

>   Just an idea how this could look
> more obvious (hopefully...):
>
> static final int SLOTS_PER_ENTRY = 2;
> static final int LOAD_PERCENT = 66;
> . . .
> int maximumCapacity = tab.length / SLOTS_PER_ENTRY * LOAD_PERCENT / 100;
> if (inserted > maximumCapactiy) {
>    // needs expansion or tombstone cleanup!
>    int newLen = tab.length;
>    if (size() > maximumCapacity) {
>      // needs expansion!
>      newLen = tab.length * 2;
>      if (newLen < 0) { throw new OutOfMemoryException("...."); }
>    }
>    Object[] newTab = new Object[newLen];
>    // do the rehash
> }
>
> Interestingly your current code would also shrink the table, since
> you calculate the next table length based on the real size. But its in the put() path :)

That's right. The consequence of "lazy" removals. The reason it is only
in put() path is that only put[IfAbsent] may insert new entry into table
and therefore increase load past the limit of 2/3. 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 think the strategy of rehash() (whether to expand or shrink or not)
should not depend on whether it is triggered by put() or remove() as
this is just the last action on the table that pushed it into a state
which needs rehashing while majority of actions preceding it could be
just the opposite. We can/should not predict the behavior of the program
from the past actions as it may be contra-productive. The most general
strategy, I think, should assume nothing from past actions and only look
at minimizing the worst-case effects considering all possible future
actions.

>
> BTW:
>
>     public int size() {
>       synchronized (lock) {
>         return inserted - tombstoned;
>       }
>     }
>
> Why not have the size as variable, and calculate occupation = size + tombstone for the internal
> purposes?

It could be that way, yes. Then 'size' could be volatile and we would
not need the lock in size(). But OTOH, size() method is not critical and
computing the occupancy at each insertion in order to check for need to
rehash is more important to be simple.

>
> Cheers,
>
> Jens
>

Thanks for your input.

Regards, Peter

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

Re: LinearProbeHashtable / Remove second volatile read?

Peter Levart
In reply to this post by Peter Levart
Hi Jens,


On 05/31/2016 09:00 PM, Jens Wilke wrote:

> On Tuesday 31 May 2016 12:44:09 Peter Levart wrote:
>> Hi concurrency experts,
>>
>> As part of an attempt to optimize the ClassValue API for small number of
>> elements per Class in OpenJDK, I came up with a proposal to leverage
>> ConcurrentHashMap, which improves the footprint overhead considerably
>> . . .
>  From concurrency / performance point of view, I wonder whether it is
> worthwhile to remove the second volatile read in get().
>
> So it would be:
>
>     public V get(Object key) {
>       Object[] tab = table;
>       int len = tab.length;
>       int i = firstIndex(key, len);
>       while (true) {
>          Object item = tab[i]; // 1st read key...
>       ...
>
> To do this, additional stores to table are needed in put:
>
>       tab[i + 1] = value; // 1st write value...
>       table = tab;
>       tab[i] = key; // ...then publish the key
>       table = tab;
>
> Cheers,
>
> Jens
>

The 1st volatile read (tab = table) is needed for correctly observing
the contents of the array as rehash() may have swapped it with newly
constructed array which was filled with relaxed writes.

The 2nd volatile read (item = getVolatile(tab, i)) is needed for
correctly observing the contents of the 'item' key (needed later in
equals() computation) as put(), for example, may have installed new key
into an empty slot. Your proposition for additional stores in put() are
not enough. For example:

PutThread:

      tab[i + 1] = value;
      table = tab;
      tab[i] = key; // not a volatile write
      // preemption and GetThread kicks in...

GetThread (racing with PutThread):

     Object item = tab[i];
     // racy read may see the key reference written by PutThread but may
also see the underlying object only partly initialized in following
actions (equals())

PutThread:

     table = tab;
     // volatile write that came to late and was not accompanied by a
volatile read of 'table' in GetThread.


The 3rd volatile read for the associated value (return (V)
getVolatile(tab, i + 1)) is needed because of put() (but not
putIfAbsent()) and replace() methods that only install new value for the
existing key. If those methods were not needed, the 3rd read could be a
normal read.

Regards, Peter

_______________________________________________
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 Peter Levart
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
Reply | Threaded
Open this post in threaded view
|

Re: LinearProbeHashtable / Remove second volatile read?

Jens Wilke
In reply to this post by Peter Levart
(re send from yesterday, since post did not make it to the list....)

On Tuesday 31 May 2016 12:44:09 Peter Levart wrote:
> Hi concurrency experts,
>
> As part of an attempt to optimize the ClassValue API for small number of
> elements per Class in OpenJDK, I came up with a proposal to leverage
> ConcurrentHashMap, which improves the footprint overhead considerably
> . . .

From concurrency / performance point of view, I wonder whether it is
worthwhile to remove the second volatile read in get().

So it would be:

   public V get(Object key) {
     Object[] tab = table;
     int len = tab.length;
     int i = firstIndex(key, len);
     while (true) {
        Object item = tab[i]; // 1st read key...
     ...

To do this, additional stores to table are needed in put:

     tab[i + 1] = value; // 1st write value...
     table = tab;
     tab[i] = key; // ...then publish the key
     table = tab;

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 / Remove second volatile read?

Jens Wilke
In reply to this post by Peter Levart
On Wednesday 01 June 2016 11:05:28 Peter Levart wrote:

> PutThread:
>
>       tab[i + 1] = value;
>       table = tab;
>       tab[i] = key; // not a volatile write
>       // preemption and GetThread kicks in...
>
> GetThread (racing with PutThread):
>
>      Object item = tab[i];
>      // racy read may see the key reference written by PutThread but may
> also see the underlying object only partly initialized in following
> actions (equals())

Interesting area to explore.

In case your example is the real execution sequence, there will be no partially
initialized object data visible, since this "happened before" volatile
store in line 2 (table = tab).

But maybe the non volatile store gets reorderd before the volatile store?
I doubt whether this is possible with the new JMM, but I cannot pinpoint the
clause that says so. Any comments on this from the JMM gurus?

Since you use unsafe anyway, you could forbid the reordering explicitly:

PutThread:

     tab[i + 1] = value; // 1st write value...
     table = tab;
     U.storeFence();
     tab[i] = key; // ...then publish the key
     table = tab;

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 / Remove second volatile read?

Peter Levart
Hi Jens,


On 06/01/2016 12:45 PM, Jens Wilke wrote:

> On Wednesday 01 June 2016 11:05:28 Peter Levart wrote:
>> PutThread:
>>
>>        tab[i + 1] = value;
>>        table = tab;
>>        tab[i] = key; // not a volatile write
>>        // preemption and GetThread kicks in...
>>
>> GetThread (racing with PutThread):
>>
>>       Object item = tab[i];
>>       // racy read may see the key reference written by PutThread but may
>> also see the underlying object only partly initialized in following
>> actions (equals())
> Interesting area to explore.
>
> In case your example is the real execution sequence, there will be no partially
> initialized object data visible, since this "happened before" volatile
> store in line 2 (table = tab).

I'm talking about the key object whose reference is written after the
volatile store in line 2.

>
> But maybe the non volatile store gets reorderd before the volatile store?
> I doubt whether this is possible with the new JMM, but I cannot pinpoint the
> clause that says so. Any comments on this from the JMM gurus?

Normal store can reorder before a volatile store. The other way around
is not possible. But that's not an issue here.

>
> Since you use unsafe anyway, you could forbid the reordering explicitly:
>
> PutThread:
>
>       tab[i + 1] = value; // 1st write value...
>       table = tab;
>       U.storeFence();
>       tab[i] = key; // ...then publish the key
>       table = tab;
>
> Cheers,
>
> Jens
>

As said, reordering of write of key reference before the write of the
table reference is not an issue here. Reordering of writes to fields of
the key object after the write of key reference is the issue. You might
say that volatile write to table in line 2 "flushes" those writes. It
does, but only if it is accompanied by a corresponding volatile read
that must be placed before reading those flushed writes, which is not
guaranteed to happen here.


Regards, Peter

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

Re: LinearProbeHashtable

Peter Levart
In reply to this post by Michael Kuhlmann
Hi Michael,


Thanks for joining the conversation.


On 06/01/2016 11:11 AM, Michael Kuhlmann wrote:

> 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

So you would never shrink the table once it grows? Maybe this is the
best strategy as other general hash table implementations have adopted
the same strategy. The specificity of this implementation is in that the
rehashing is triggered not because of size() growing over loadFactor *
capacity but because of size() + tombstoned growing over loadFactor *
capacity, so doubling the capacity with each rehashing is not always
appropriate. So maybe the rehash() strategy should just decide between
keeping the old capacity or doubling it in a way that doesn't cause
frequent rehashing.

Regards, Peter

>
>
> _______________________________________________
> 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 / Remove second volatile read?

Jens Wilke
In reply to this post by Peter Levart
On Wednesday 01 June 2016 13:12:00 Peter Levart wrote:
> It does, but only if it is accompanied by a corresponding volatile read
> that must be placed before reading those flushed writes, which is not
> guaranteed to happen here.

But that is exactly what you do in all your code paths:

  Object[] tab = table;

You never can see a partially initialized key object in case the reference
never becomes visible before the rest.

As you step over the line above, either the object contents are visible, because of
the first volatile store, or the reference and the contents are visible, because of
the second volatile store.

Do I miss something?

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

Michael Kuhlmann
In reply to this post by Peter Levart
Hi Peter,

Am 01.06.2016 um 13:28 schrieb Peter Levart:
> So you would never shrink the table once it grows? Maybe this is the
> best strategy as other general hash table implementations have adopted
> the same strategy. The specificity of this implementation is in that the
> rehashing is triggered not because of size() growing over loadFactor *
> capacity but because of size() + tombstoned growing over loadFactor *
> capacity, so doubling the capacity with each rehashing is not always
> appropriate. So maybe the rehash() strategy should just decide between
> keeping the old capacity or doubling it in a way that doesn't cause
> frequent rehashing.

Usually I wouldn't. But in your case, it's different because the list
might get filled with tombstones over the time, if it's never rehashed.

Maybe this can be solved differently. I wonder whether it was a good
idea to invent the skip factor in the tombstones. If you stay away from
that, and just iterate over all tombstones like as with normal values in
the get() method, you gain one advantage:

In the put() method, if a tombstone is identified, you can simply
overwrite it with the new value. In that case, the number of elements +
tombstones never will get much higher than the maximum number of
elements over all time.

And on top, the tombstone instance can be a singleton enum value (and
identified by identity check).

The disadvantage is that get() probably needs to iterate over some more
tombstones if many values have been removed.

But on the other side, when the same key gets removed and added several
times (which might be a common use case), you won't get a large list of
tombstones which would block some area of your array, raising the chance
of hash collisions with other elements.

So, in total I would assume that a skip-less tombstone approach is a
performance gain.

Or do I miss something?

-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

Jens Wilke
On Wednesday 01 June 2016 15:02:53 Michael Kuhlmann wrote:
> In the put() method, if a tombstone is identified, you can simply
> overwrite it with the new value.

Be careful. See the read path:

 123     public V get(Object key) {
 124         Object[] tab = table;
 125         int len = tab.length;
 126         int i = firstIndex(key, len);
 127         while (true) {
 128             Object item = getVolatile(tab, i); // 1st read key...
 129             if (key == item || (item != null && key.equals(item))) {
 130                 // possible race with removing an entry can cause the value
 131                 // to be observed cleared. If this happens, we know the key
 132                 // has/will be tombstoned just after that so null is returned
 133                 return (V) getVolatile(tab, i + 1);  // ...then value

What happens if a thread stops before line 133? For removal you can safely write a null. If you write
another value, you assign it possibly to a key that was there once there a while ago.

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

Peter Levart
In reply to this post by Michael Kuhlmann
Hi Michael,


On 06/01/2016 03:02 PM, Michael Kuhlmann wrote:

> Hi Peter,
>
> Am 01.06.2016 um 13:28 schrieb Peter Levart:
>> So you would never shrink the table once it grows? Maybe this is the
>> best strategy as other general hash table implementations have adopted
>> the same strategy. The specificity of this implementation is in that the
>> rehashing is triggered not because of size() growing over loadFactor *
>> capacity but because of size() + tombstoned growing over loadFactor *
>> capacity, so doubling the capacity with each rehashing is not always
>> appropriate. So maybe the rehash() strategy should just decide between
>> keeping the old capacity or doubling it in a way that doesn't cause
>> frequent rehashing.
> Usually I wouldn't. But in your case, it's different because the list
> might get filled with tombstones over the time, if it's never rehashed.
>
> Maybe this can be solved differently. I wonder whether it was a good
> idea to invent the skip factor in the tombstones. If you stay away from
> that, and just iterate over all tombstones like as with normal values in
> the get() method, you gain one advantage:
>
> In the put() method, if a tombstone is identified, you can simply
> overwrite it with the new value. In that case, the number of elements +
> tombstones never will get much higher than the maximum number of
> elements over all time.
>
> And on top, the tombstone instance can be a singleton enum value (and
> identified by identity check).
>
> The disadvantage is that get() probably needs to iterate over some more
> tombstones if many values have been removed.
>
> But on the other side, when the same key gets removed and added several
> times (which might be a common use case), you won't get a large list of
> tombstones which would block some area of your array, raising the chance
> of hash collisions with other elements.
>
> So, in total I would assume that a skip-less tombstone approach is a
> performance gain.
>
> Or do I miss something?

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

Regards, Peter

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

Peter Levart



On 06/01/2016 03:50 PM, Peter Levart wrote:
Or do I miss something?

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

Regards, Peter

If I could keep the keys in the table after the entries are removed (simply by clearing the value slots), then I could reuse such "removed" entry at least for re-insertion of the same (equals) key. But it is usually expected from a Map that it releases both key and value when the entry is removed, so that they can get GC-ed.

Peter


_______________________________________________
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 01.06.2016 um 15:56 schrieb Peter Levart:

>
>
> On 06/01/2016 03:50 PM, Peter Levart wrote:
>>> Or do I miss something?
>>
>> 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".
>>
>> Regards, Peter
>
> If I could keep the keys in the table after the entries are removed
> (simply by clearing the value slots), then I could reuse such "removed"
> entry at least for re-insertion of the same (equals) key. But it is
> usually expected from a Map that it releases both key and value when the
> entry is removed, so that they can get GC-ed.
>
> Peter
>


You're right. I missed the point that the sequence put(a, x); remove(a);
put(b, y) would make it possible to return y in get(a).

Adding some kind of Entry object with key and value combined, like in
HashMap, is not an option? This would help with that problem. But of
course, it would raise the memory footprint slightly.

Hmh...

-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 / Remove second volatile read?

Peter Levart
In reply to this post by Jens Wilke


On 06/01/2016 02:06 PM, Jens Wilke wrote:

> On Wednesday 01 June 2016 13:12:00 Peter Levart wrote:
>> It does, but only if it is accompanied by a corresponding volatile read
>> that must be placed before reading those flushed writes, which is not
>> guaranteed to happen here.
> But that is exactly what you do in all your code paths:
>
>    Object[] tab = table;
>
> You never can see a partially initialized key object in case the reference
> never becomes visible before the rest.
>
> As you step over the line above, either the object contents are visible, because of
> the first volatile store, or the reference and the contents are visible, because of
> the second volatile store.
>
> Do I miss something?
>
> Cheers,
>
> Jens
>

Ok, let's write down some more context:

GetThread:

      tab = table;
      // preemption and PutThread kicks in...

PutThread:

      key = new Key(...);
      table.get(key);
      ...
      tab[i + 1] = value;
      table = tab;
      tab[i] = key; // not a volatile write
      // preemption and GetThread kicks in...

GetThread (racing with PutThread):

     Object item = tab[i];
     // racy read may see the key reference written by PutThread but may
also see the underlying object only partly initialized in following
actions (equals())

PutThread:

     table = tab;
     // volatile write that came to late and was not accompanied by a
volatile read of 'table' in GetThread.


You see, volatile read of table in GetThread might be performed before
the volatile write of table in PutThread.


Regards, Peter

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

Re: LinearProbeHashtable

Peter Levart
In reply to this post by Michael Kuhlmann


On 06/01/2016 04:05 PM, Michael Kuhlmann wrote:

> Am 01.06.2016 um 15:56 schrieb Peter Levart:
>>
>> On 06/01/2016 03:50 PM, Peter Levart wrote:
>>>> Or do I miss something?
>>> 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".
>>>
>>> Regards, Peter
>> If I could keep the keys in the table after the entries are removed
>> (simply by clearing the value slots), then I could reuse such "removed"
>> entry at least for re-insertion of the same (equals) key. But it is
>> usually expected from a Map that it releases both key and value when the
>> entry is removed, so that they can get GC-ed.
>>
>> Peter
>>
>
> You're right. I missed the point that the sequence put(a, x); remove(a);
> put(b, y) would make it possible to return y in get(a).
>
> Adding some kind of Entry object with key and value combined, like in
> HashMap, is not an option? This would help with that problem. But of
> course, it would raise the memory footprint slightly.

If I do that, then I might as well change the table to use chained
nodes. But that's what we already have in ConcurrentHashMap.

The whole point of this implementation was to have a more direct access
to key/value which improves cache-locality and with it, access time.

>
> Hmh...
>
> -Michael

Regards, Peter

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

Re: LinearProbeHashtable / Remove second volatile read?

Peter Levart
In reply to this post by Peter Levart
Sorry, I just noticed I made a mistake here...


On 06/01/2016 04:08 PM, Peter Levart wrote:

>
>
> Ok, let's write down some more context:
>
> GetThread:
>
>      tab = table;
>      // preemption and PutThread kicks in...
>
> PutThread:
>
>      key = new Key(...);
>      table.get(key);

The above line should read:

         table.put(key, ...);

>      ...
>      tab[i + 1] = value;
>      table = tab;
>      tab[i] = key; // not a volatile write
>      // preemption and GetThread kicks in...
>
> GetThread (racing with PutThread):
>
>     Object item = tab[i];
>     // racy read may see the key reference written by PutThread but
> may also see the underlying object only partly initialized in
> following actions (equals())
>
> PutThread:
>
>     table = tab;
>     // volatile write that came to late and was not accompanied by a
> volatile read of 'table' in GetThread.
>
>
> You see, volatile read of table in GetThread might be performed before
> the volatile write of table in PutThread.
>
>
> Regards, Peter
>

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