One Hour One Life Forums

You don't need to do anything.  It uses only 80MB, 160+768 is free.  Almost all is in cache because that's the only sensible use for it in this situation.  Once some program starts using it, system will reclaim almost all of it.

If it fits in cache, it shouldn't matter.  If it doesn't, it'll be 100-1000 times slower.

That's the weakest point of its design.  The goal is to get right hash function and load low enough for keep longest chain to 2-3 items.  Almost all items should be in first table.

it uses 8 bytes per hash table pointer.  You can halve memory use it by changing uint64 to 32 (will alter disk format as well).

I would ignore insert performance for now.  Most of it is from writting huge hash table once.

When you ignore initial insert and final seq scan it's not:

KDB Random look used 0 bytes, took 2.839000 sec
SDB1 Random look used 0 bytes, took 4.563000 sec
SDB2 Random look used 0 bytes, took 5.093000 sec

KBD Last-inserted lookup used 0 bytes, took 2.056000 sec
SDB1 Last-inserted lookup used 0 bytes, took 2.033000 sec
SDB2 Last-inserted lookup used 0 bytes, took 3.058000 sec

KBD Random look/miss used 0 bytes, took 1.365000 sec
SDB1 Random look/miss used 0 bytes, took 3.774000 sec
SDB2 Random look/miss used 0 bytes, took 2.468000 sec

KBD Inserts after miss used 31997952 bytes, took 6.675000 sec
SDB1 Inserts after miss used 0 bytes, took 5.525000 sec
SDB2 Inserts after miss used 0 bytes, took 7.326000 sec

12M or 120M rows?  It uses 8 bytes/hash entry/table.  With 3 tables it's 300M for 12M rows.  Changing uint64 to 32 will halve it.  150M.  Well, I had hundred times more RAM in my previous laptop.

BTW. I don't suggest that as a final solution.  Just quick and dirty way to fix lag issues for now, until better solution is implemented.

But if you miss, you put down the knife.  Then if it's real griefer, not noob, he'll pick it up and now he has two knifes and you have none.  GG.  You may have next occasion to practice next week.  So a very slow way to learn how to fight.  The only way to train is to become griefer yourself.  That's why I asked for practice weapons:
https://onehouronelife.com/forums/viewtopic.php?id=2145

After all you don't practice fight with real weapons with you colleague, and then rush him up to hospital to prop him up before next session.  At least most people don't do that.  Those which do end up with darwin award and life prison sentence respectively.

I thought about this.  It's not that usefull in this case.  It needs ~10 bits per key for 1% false positive rate with random access all over it, so you'll pretty much have to keep it in RAM and it'll grow proprtional to number of records in db.  You'll need to completely recreate it from time to time to keep 1% false positive rate with increasing number of records.  And it will deal with part of the problem only - null lookups.  Getting old data will still cause lag with hundreds of reads mulitplied by hundred tiles/thousand items and subitems.  Fixing that will need fix to underying structure anyway and then your bloom filter will be useless.  So it's waste of time IMO.

Yep, he is really oldskool.  Maybe we should keep him around as endangered species.  And his posts work very well as litmus test for anti-griefer solutions.  The more insults you get, the better the outcome.

They are always faster and more space efficient that trees.  You use trees only if you want in order iteration.

The wrong assumption you're making is that you should keep hash table size static.  In practice you do it only if you know in advance how big you dataset will be.  For every other use case, if load gets too high (say >50%), you double the size and rehash, if it gets too low (say <25%) you halve its size and rehash.

It deals with all problems there.  And it pretty simple, if you know what it tries to achieve.  Usually if load gets too high, you just allocate new table twice as big and rehash everything.  This still gives you amortized O(1) so it's fine for most purposes.  It's not fine when you have real-time application, because you then have this huge spike from time to time.

Linear hashing deamortizes it, by extending hash table by one bucket at a time instead of everything at once.  It takes first unsplit bucket and moves half of elements to the new bucket at the end.  Then for lookup you need to take this into account.  You have three zones: first zone at the beginning holds already split buckets, middle one holds yet unsplit buckets and at the end you have section of split buckets the same size as first.  So to get an item you need to figure out in which section your bucket is and use new hash for first and third section and old hash for middle one.  That's all.

Because they are the best if you don't have some additional requirements like order of iteration.  Heresey here is keeping their size static no matter the load and expecting good performance.  If you go over recommended load (50-85% depending on collision handling) it degenerates from nearly perfect O(1) structure into totally useless O(N) one.

and curse points

Did you clear disk cache between profiler runs?  It may not be a problem now with warm cache, but it will be if db size grows larger than RAM.  You'll hit very steep performance cliff when WDS gets larger that RAM.

And later on, if you would like to optimize responses below 1ms you will hit this bottleneck even with few I/O requests per user request.  But that's the problem for future Jason

That's mostly what I implemented, with two important improvements from paper I quoted - linear probing instead of chains and then extending hash table on overflow in last bucket, instead of wrap around.

BTW. Over the weekend I wrote most of the implementation for Linear Hashing (KissDB API compatible).  If you're interested I may contribute it, once I have unittests with good coverage.  I does keep O(1) gets (including misses) and inserts, no matter how much data you put there.

So things I've suggested blindly would have fixed the problem.  This one solves it completely:

And this one would reduce lookups hundredfold:

I think this one will be also necessary later on to get to sub ms responses:

That's what you need:
Linear Hashing with Overflow-Handling by Linear Probing
http://www.cs.tau.ac.il/~shanir/advance … larson.pdf

Note that if you keep load <50% (and for real time app I would recommend to do so) significantly simpler algorithm would do.  You can get rid of multiple passes/swipes.  They are only needed if you want to save space and keep load at 80-85%.  But that costs few lookups for each get and insert, so it's kind of bad tradeoff for real-time app.  Disk space is cheap.

Hash tables ars O(1) whp.  At this point you have bunch of linked lists, not hash table.  Hash tables work fine with load up to 50%-85% (depending on how you handle collisions).  You run it with load of 15200%, so it degenerated into linked list.

And probably milk from cows.