One Hour One Life Forums

Map chunks and map updates include item info as well - you can see full data in replay files, not stdout.  Map chunks are gzip compressed though, so just text editor won't be enough to view it.

I find one analogy very useful and helpful in deciding how to optimize code.  Change times that processor see to human scale.  It goes like this:  Getting data from register - just recalling something quicky - 1 second.  Getting data from L1 cache - finding and reading some number on screen - few seconds.  Getting data from L2 cache - reading few sentences - 15 seconds.  Getting data from main memory - going to other room, finding book and correct chapter, reading a page or two, going back - 5 minutes.  Getting data from SSD - jumping into a car, driving to nearby state, reading some document there and driving back home - 10 hours.  Getting data from spinning disk - flying to India, going on long trip to many different places, talking to many people in search of some old manuscript, finally finding it, reading it and flying home - 1 year.  Getting data from user in Europe across Internet - launching space probe to go to Jupiter, taking photo there and flying back - 20 years.

So far you figured out that sending a novel to users word at a time wouldn't work.  They'd get lost in plot.  So when they send request, you prepare a full page and send it.  But you still think that driving 10 hours to nearby state and back to get one word at a time works great. "It just takes couple of months per user, no big deal.  Look, I have this awesome system: for every word I bring, I print a page with all information required to know where it came from: chapter, page, sentence and word number in sentence.  I have lots and lots of stacks of papers like that.  And I also found out that very frequently I'm asking about a word far into sentence, but sentence is too short.  So I also print out a papers that let me know, that in chapter 7 on page 21 in sentence 15 there is no word number 17!  This system works amazingly good!"

I've been suggesting for some time, that if you're driving to the other state, don't bring just single word every day.  Bring xero of the whole page.  In one day you'll do serveral months worth of work.  But now I have even better idea.  Bring the whole fricking book home!  So when you need to read something, you just go to the other room.  -Fit the whole book in my home?  Impossible, look a all those stacks of the papers.  I constantly run out of space and need to throw some of them out.  -Well, if you don't keep single word per page, I'm sure it'll fit.  -But I have to amend this book every day!  What if tornado hits my home?  All work will be lost!  -Send every day a letter listing all changes you've made to the other state.  So if something goes wrong, the latest version of the book can be reconstructed.  -But this will generate infinite number of papers with changes.  I couldn't store that!  -Then from time to time let someone apply all the changes and bind new edition of the book.  Then you need to store only recent changes.

No, this proposition is not a joke.  Keep state in RAM.  Currently for every 21 bytes you write, you store only maybe 2 bytes of actual data.  That's like 90% overhead.  Keys give also some infromation, but they are highly correlated.  They hardly have more than additional bit or two of entropy.  And half of the cells are empty.  So your complete state will be smaller than the table with fingerprints you prepare, to know that "nothing is there".  Open append-only file, log every change which should persist across reboots.  On restart parse change log and rebuild the state.  Then write snapshot of state, so you don't need start always from beginning.  You can also do it incrementally.  Every 100k changes switch to new file.  Let some background process go through log entries and dump resulting state - a shorter list of changes.  No database schemas to keep.  No migrations.  -What if I run out of RAM?  -Pay 5 bucks, double the RAM, reboot.

Correct.

We cannot do this blindly, but sometimes split will create hole that is legit.

You don't need to bother yourself with elements to the left - you've already handled them in previous splits.  And yes, you need to handle the whole island to the right, possibly moving some elements back.  They cannot be moved into arbitrary bucket, though, only as far left as their primary bucket (the one they would hash into without collisons/overflows).  This process may create holes or some elements may jump over the ones that cannot move.

IMO the best way to handle it is to split all buckets in an island in one go.  You need to analyze them anyway, figure out where they should go, write ones that move, create some holes.  And on next split you will be analysing it all over again.  So better just split all the buckets up to and including trailing empty one in one go.

You can with marking element as deleted, so linear probing will know to not stop there.  But it's completely counter productive - you'll end up with longer and longer chains.  So, you want to move elements back closer to their primary bucket and create holes that stop linear probing.

The best way to handle it is to avoid it altogether - never wrap around.  When collision/overflow happens in last bucket, just create new one following it.  It should be marked as special, because it's not normal split bucket yet (so you know where next split should happen even if you quit app and restart later).  On next split, you need to take overflown elements into consideration, possibly creating next overflow bucket(s).

Because you cannot write 21 bytes to disk.  You must write whole sector, usually 4k.  That turns write into read-modify-write.  If sector is not in cache, it needs first to be brought in.

Also, for sequential writes, clib will buffer some data first, so it'll take fewer syscalls to write data, which are quite costly.  May not need as many file seek syscalls as well.

Just few hints.  Instead of 80k single item buckets use eg. 4k 20 item buckets - that will even out random spikes.  And won't be slower, because you cannot get less than a block from disk anyway.

Prefetch 4-8 buckets on read.  If bucket is full, you'll have next already in RAM.  Unless you run massively parallel I/O, you won't see any slowdown.

I proposed the same:
https://onehouronelife.com/forums/viewt … 350#p25350

Originally as idea how to get rid of map wipes.

I've run few test and I think I know what happend.  The modulo with 32 bits hash gave tiny bias (<1%), but the main thing is: if you put 15M items randomly into 30M bins, you get distribution looking more or less like this:
Counter({0: 18196821, 1: 9096015, 2: 2275788, 3: 378792, 4: 47342, 5: 4811, 6: 409, 7: 20, 8: 2})
aka birthday paradox

So the funny thing is, djb2 got so good results precisely because it is so bad   In that particular case it worked more like counter than hash.

I wouldn't feel safe with keeping djb2.  It turned out to be in our favor here, but may quickly degenerate into massive number of collisions as well.

The solution is simple, but not trivial.  Use smaller number of larger buckets to flatten it out.  If you use 30M 1 item buckets expected max chain length is 8.  If you use 15M 2 item buckets, it's 5.  With 7.5M of 4 items buckets it's 4.  With 1.5M 20 item buckets it's 2 (slight overflow - I've got 29 items in largest one).

Or maybe switch to StackDB with large hash table.  Having 8 items in longest chain shouldn't give much problem.

Without debugging I don't know.  I certainly would expect it to perform better.  Heck, djb2 is as weak as you can go.  It's just bit shift and add.  My first reaction to seeing something like that would be to change it to at least "on each round multipy by prime, take middle bits where most mixing occurs".

Without debugging it further, maybe just switch to SipHash and see what happens.  If it also behaves badly, you have some serious problem worth investigating.

Beware that there may be a bug.  If you hold a baby, name yourself, then name baby, the baby sometimes still will be nameless.  I hit this bug at least two times already, maybe more.  I even sent replay to Jason showing it, but there is no fix yet.

So workaround for now is: name yourself, put down baby, pick up baby, name the baby.  This works fine.

Max bin depth = 3

I wonder how it got down from 4 to 3.  Is there some non seeded randomness involved?

Random lookup for 500 batchs of 3000 (1500000/1500000 hits)
Random look used 0 bytes, took 3.932000 sec

That's ~400k lookups/s - pretty good.

Last-inserted lookup for 500 batchs of 2401 (1200500/1200500 hits)
Last-inserted lookup used 0 bytes, took 3.122000 sec

Same.

Random lookup for non-existing 500 repeating batchs of 3000 (0/1500000 hits)
Random look/miss used 0 bytes, took 2.265000 sec

650k null lookups/s - when served from RAM & cache.

Random lookup for non-existing 1500000 non-repeating values (0/1500000 hits)
Random look/miss used 0 bytes, took 13.899000 sec

100k null lookups/s - when it needs to touch the disk half the time.  That's pretty good too.  SSDs can handle ~100k IOPS, so we're using 50% of capacity.  Pushing for more would require issuing requests in parallel.

Inserts for previously non-existing 500 batchs of 3000
Inserts after miss used 240001024 bytes, took 10.301000 sec

150k inserts/s.  Again, we're hitting disk.  It will be faster for small batches.  Here we see steady state when things need to be pushed on disk.

Anyway most of the time here is spent on adding 4th hash table.  We're going from 50% to 55% load.  I'd recommend to keep in under 50% all the time.  So after reducing memory usage just start with ~40% load.

I agree we should stop talking about it, just do it and pretend it never happens