@hyc@mastodon.social cover
@hyc@mastodon.social avatar

hyc

@[email protected]

CTO Symas Corp., Chief Architect OpenLDAP Project, Musician

This profile is from a federated server and may be incomplete. View on remote instance

pervognsen , to random
@pervognsen@mastodon.social avatar

PSA: If you construct a B-tree with splitting-based inserts then constructing the tree from items in key-sorted order is actually the worst case for packing efficiency. Every node/leaf ends up exactly 50% full except for the right spine. When you bulk-construct a tree from scratch from sorted items, you want to do the construction bottom up and you don't want to use splits. That's linear time and yields an optimally packed tree (everything full excerpt for a partially packed right spine).

hyc ,
@hyc@mastodon.social avatar

@pervognsen you don't need to change the build order for in-order inserts. You only need to change the page-split strategy. This is what LMDB's MDB_APPEND mode does for in-order loading. When a page is full we just start filling a new page instead of splitting the current page. It gives effectively linear construction speed without having to introduce a completely new code path.

hyc ,
@hyc@mastodon.social avatar

@pervognsen but optimal packing isn't necessarily ideal, particularly if the data is non-consecutive and will have inserts interspersed in the future. LMDB addresses this too.

hyc ,
@hyc@mastodon.social avatar

@pervognsen if we see that new records are coming in-order, but MDB_APPEND wasn't specified, we bias the split 70/30 instead of 50/50. So the new page has more room, and the old page can still accept inserts in the future.

hyc ,
@hyc@mastodon.social avatar

@pervognsen yeah, the textbook description of B+tree behavior leaves a lot to be desired (and discovered, for a new implementor!) when tossed into the real world. I touched on this in the "Dark Underside" section of my Databaseology talk. https://www.youtube.com/watch?v=tEa5sAh-kVk

pervognsen , (edited ) to random
@pervognsen@mastodon.social avatar

How much RAM do you have in your dev workstation/laptop?

hyc ,
@hyc@mastodon.social avatar

@pervognsen 128GB wasn't an option when I bought, so making do with 64GB.

regehr , to random
@regehr@mastodon.social avatar

I've been seeing more posts recently about AIs getting poisoned by training on AI bullshit, but this reminds me of the time I assigned students to go find a red-black tree implementation on the web and then test it and fix the bugs they found. most of the available implementations were so wrong that the assignment was infeasible, and this was well before the current wave of AI-generated bullshit.

hyc ,
@hyc@mastodon.social avatar

@regehr reminds me, I never got my AVL tree completely right back in college. I got it working fine for left inserts, and then just inverted some conditionals for right side, but something always broke there. The homework assignment had us turn in the code with our own tests, so I just chose my test data to avoid the broken cases. Got full credit on that assignment.

hyc , to random
@hyc@mastodon.social avatar

Tfw you're midway thru the red-eye return flight to Europe from the US, and you're going to swap the US SIM card out of your phone, and you push a paperclip into the SIMcard holder's eject hole, and it pops out suddenly and you see the microSD and SIM cards go flying into the darkness.

hyc OP ,
@hyc@mastodon.social avatar

@pervognsen definitely tends toward the disastrous, yeah. Fortunately they didn't get far.

arstechnica , to random
@arstechnica@mastodon.social avatar

FCC scraps old speed benchmark, says broadband should be at least 100Mbps

Standard of 100Mbps down and 20Mbps up replaces old 25Mbps/3Mbps benchmark.

https://arstechnica.com/tech-policy/2024/03/fcc-scraps-old-speed-benchmark-says-broadband-should-be-at-least-100mbps/?utm_brand=arstechnica&utm_social-type=owned&utm_source=mastodon&utm_medium=social

hyc ,
@hyc@mastodon.social avatar

@arstechnica 25/3 sounds about like what I got in LA. Meanwhile, out here in the wilds of rural northwest Ireland, I've got 1000/100 FTTH.

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • random
  • tech
  • kbinEarth
  • testing
  • interstellar
  • wanderlust
  • All magazines
    •