FAQ
Oh, and you prettied it up, thanks!

My tests look like it's something like 40% slower to add the mutex, but it
definitely exhibits the same GC behaviour, which is great.

I think that my initial logic is supposed to be race-safe, although it
might only be race-safe with atomic writes of, separately, the key and the
value -- here's how I was thinking about it.

With atomic writes of key and atomic writes of value:

0) On empty key or key == mykey
  1) Atomically write key
  2) Atomically write value
  3) Check lookup[key] == value
     A) If yes: done
     B) If key != mykey: give up the key and start over. Either there's a
second write to the same key, or someone else has claimed this slot before
1 and written to it after 1. They can have it.
     C) If val != myval: We own this slot, stubbornly rewrite it.

I think you can even relax the atomic write on key, since in a race where
the key is half-written by either side (is this even possible in Go?) the
entry will get corrupted, and both threads will bomb out at 3B, leaving a
corrupted entry in the hashtable. For my use cases this would be fine, but
certainly not everybody's.

I suppose that you could have a race where two threads set the same key to
different values. I think there what happens is that first to successfully
get both written will lose and give up, thinking they were successful. The
other will wipe that value and be happy.

The only one that's worrisome to me on reflection is this one: you could
also potentially have a race where thread 1 sees empty, then halts all
execution. Thread 2 sees empty, sets, returns happily. Thread 1 writes and
checks and sees everything is good. Thread 2 got its data clobbered. I
can't tell right now thinking about it if implementing Compare and Swap on
the setting step fixes this last condition, but the blog post claims it
does. :)

  Thanks again for the update, I will fork it back into my work for sure.
I'm not decided on implementing CAS or using the mutexed version you've got.

Peter



On Saturday, January 24, 2015 at 4:28:01 AM UTC-8, Tamás Gulácsi wrote:

2015. január 24., szombat 10:32:23 UTC+1 időpontban Peter Vessenes a
következőt írta:
Thanks for the input everyone.

I whipped up a lock-free, pointer-free hash table library after reviewing
Caleb's. If Caleb's wasn't safe for primetime, this is DEFINITELY not safe.
Do not use except for play. Here's the gist:
https://gist.github.com/vessenes/ce7d1254ad92c6d2a996

The package assumes you want to map a record type to an int offset, which
would presumably be used to get your data out of an array. It could be
easily reworked to store any sort of fixed length data with similar
performance characteristics. It doesn't resize the table, but it can tell
you if you're out of space, and will return an error.

The good news is that this has the expected characteristics. A size 1
billion hash table with 500million elements can be garbage collected in
150ms on my beefy server. (The first GC costs like 20seconds, subsequent
are fast.) So, thanks for the help! That's like a 40GB or so data
structure. Lookups are in the hundreds of nanoseconds.

The lock free algorithm I used is a naive <<--- implementation of
http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/.
It seems to work pretty well; I instrumented the gist with a bunch of
command-line options to play with. A multi-core friendly hash table on my
system is a LOT faster than single core; this particular one runs about 10x
the speed using all 40 cores compared to single threaded.

Anyway, thanks guys! This is a big help, and a fun learning experience.

Lock-free, but not race-free - run with "-race"!
I've updated it to use sync.RWLock, but only two continuous slices:
https://gist.github.com/tgulacsi/549c8797cfd9a21f03bb
No pointers, no allocation, so I think it is absolutely GC-friendly.
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 11 of 23 | next ›
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJan 23, '15 at 11:46p
activeFeb 1, '15 at 1:47a
posts23
users11
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase