HN user

btym

547 karma

-

Posts4
Comments145
View on HN
Vim.wasm 7 years ago

The actual issue is that Windows and Linux don't properly use a ‘super’ key―while the ‘Win’ key is sitting there uselessly.

These keys are great to use on Mac

The use of the super key on Mac is horrible. It should sit there uselessly, until I tell it to do otherwise. On Mac, here are no safe hotkeys to bind anything to. On Linux, my WM configuration has a ton of actions bound to the super key, and I never have to worry that it will conflict with another application.

And so our "two loops" are usually just "do two simple SIMD operations". Not quite so offensive when you say it like that!

No, it's not quite so offensive, but this doesn't explain why it's the best option. Is there no equally-fast way to write the first-tombstone implementation with SIMD instructions? The answer seems to be in the sketch of the implementation, which I'm having trouble understanding.

EDIT: I'm watching the original SwissTable talk now... would it really have been worse to use 2 bits for empty/tombstone/full/sentinel, and 6 bits for hash prefix?

EDIT 2: More implementation info. Tombstones are actually rare, because if any element in your 16-wide chunk is empty, you don't have to create a tombstone. In the very best case (a perfectly distributed hash function), your hashmap has to be ~94% full before it's even possible to fail this. Because tombstones are so rare, it's better to save the single bit for extra confidence in the hash prefix.

So, here is my understanding of the implementation and its rationale:

* Every bucket in the backing array has a corresponding byte in a metadata array

* 1 bit of this byte stores whether the bucket is empty, the other 7 bits are for a hash prefix

* SIMD instructions search 16 bytes at a time, checking: this bucket is not empty, this bucket's key matches the first 7 bits of my key

* Since 16 buckets are checked for emptiness at the same time, you can avoid creating a tombstone for a bucket if any of the other 15 buckets are empty (just set it to empty, i.e. set the first bit to 0)

* This means that tombstones are very unlikely- you'll probably rehash before you get to the load factor where you start seeing tombstones

* Since tombstones are so unlikely, it's more valuable to add an extra bit to the hash prefix than it is to quickly find tombstones

My question remains: why can't the first search return the offset of the first empty bucket? In this loop, why is there not an else that saves the offset?: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...

I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?

My argument was only that bringing the cost down would make it easier to build a more reliable P2P network. I doubt that reliability/cost are the main reasons P2P networks aren't more popular, rather that the average person doesn't really care or even know about their existence.

That's not what's happening, though. Brave is not running a streaming video service. They aren't hosting or distributing the content. There's nothing illegal about holding money and pledging to give it to someone if they ask for it (as long as you actually do).

EVERY OTHER CONNECTOR has gone through improvements. new USB standards. new video. everything. why is this any different?

Physical improvements have been necessary for USB to increase bandwidth. 3.5mm is a connector for carrying two (sometimes 3) analog signals, and backwards-incompatible changes aren't necessary until we develop a third ear.