CppCon 2017: Allan Deutsch “Esoteric Data Structures and Where to Find Them”

—
—
We already have array, vector, and unordered_map, what other data structures could we possibly need?

As it turns out, there are a lot of them and they come from all areas of software! Curious to learn the latest method of representing a pathfinding search space in detailed 3D environments? Does efficiently detecting if a website could be malicious sound like an interesting problem to you? Perhaps understanding how AAA games store and track their entities so efficiently is more your speed?

All these things and more can be yours in exchange for just one hour of your time! Using that hour we will delve into some of the unique challenges faced by C++ developers in a variety of domains, and learn the inner workings of the creative solutions devised to solve them.
—
Allan Deutsch: DigiPen Institute of Technology, Student

Allan Deutsch is a BSCS student at DigiPen Institute of Technology.
He has a passion for performance, an interest perfectly paired to C++ and game development. Allan completed a software engineering internship at Microsoft in 2016 and will be returning as a program manager intern in 2017 working with the Xbox Advanced Technology Group. He is currently working on proposals to the C++ Standards Committee for more efficient data structures, as well as the accompanying reference implementations. In his free time, Allan enjoys sailing, SCUBA diving, lifting weights, and organizing events.
—

*-----*
*-----*

[cacheman]

0:36 Slot map
10:08 Bloom filters (non-counting)
16:46 Navigation meshes
20:36 Hash pointer / Block chain / Merkle tree

[tommasobonvicini]

"So the guarantees of a slot map are that it has true constant time lookup, erase and insert operations, so rather than being amortized, these will always be at fixed cost ... with the one exception that insert will be O(n) when it needs to reallocate and grow"

BUT THAT'S EXACTLY WHAT CONSTANT AMORTIZED COST IS!

[danwu]

7:50 why does dense storage cause unstable addresses? what does the "unstable addresses" mean anyway?

[von_nobody]

Merkle tree could be used to represent game state, some workers update data and change hashes, at beginning of next stage you can easy detect what was change and update/recalculate only things that need be changed.

[xinpingzhang]

12:08 "They are generally implemented as a red-black tree" How do we implement a HashSet using red-black tree?

[apojoga]

I'm unclear why slot_map needs to keep the data contiguous.

[Xeverous]

Isn't the slot map similar to proposed pff::colony?

[waffleboot]

I don't understand how did you define slot for last element at 6:37? You update slots[6] from index 7 to index 4 after erasing element but I don't see direct links from data to slots.You know last element but how did you define that it has corresponding slot at position 6? Am I right that you try to find slots element where index is 7 for updating it to 4 but it takes O(n) ?

[llothar]

Bloom Filter shouldnt be seen as esoteric because they are so useful

[meowzerus]

6:35, On the topic of slot maps. "Then we need to find the entry in the slots table" is describing an O(N) operation. To have true constant time additions, you need an extra table that maps from data to slot, adding a little more complexity to the implementation. This slide deck explains the concept of slot maps well, but is incorrect on parts of the implementation.

[strictnonconformist]

I absolutely hate up-speak? People making question-statements are confusing?

I’m hearing this defective form of speaking more and more, and it causes confusion quite often. And yes, I do live in the area where this speaker is attending school, but I’m sure this speech pattern isn’t limited to this area.

If you’re sure of what you’re saying as a statement, don’t make it sound at all like a question by tone of voice: if you’re asking a question, don’t make it at all sound like (by grammar and word order) like a statement.

If someone uses up-speak to interact with me where there is anything I can gain by choosing how to nterpret it, I will interpret it to my best advantage and tell them so. If they get offended or upset, I’m fine with that: stop wasting my time with your stupid lazy speech anti-pattern!

[DareToSavorVanillaWithBacon]

5:35 - "And so, we're gonna put our data there and then, moving forward, we have to pop something off the free list head..."
Moving what forward, did I miss an iterator or something? Oh, right, corporate speak. I should make such speech one of my stretch goals by the end of play, right after I touch base with a coworker, since both of us need a thought shower.