Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why databases use ordered indexes but programming uses hash tables

evanjones.ca

Post reply on HN
Print view View original

161–170 of 205 posts

Re: Why databases use ordered indexes but programming uses hash tables

#161

Post by AstralStorm »

kccqzy wrote: post #122
loeg wrote: post #88

Earlier quoted context omitted.

Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.

Cache locality issues can be fixed by using a good allocator (or a good compacting GC).

How can an allocator optimize the layout of a dynamically sized structure that's being changed without compacting?

Now, compacting is an O(n) memory move plus additional calculation to figure out optimal-ish layout.

(Can be amortized, but it's same as amortizing hash table resizing. Optimal layout cannot be decided without profiling, and that's expensive.)

Re: Why databases use ordered indexes but programming uses hash tables

#162

Post by tom_ »

Thorrez wrote: post #133
LessDmesg wrote: post #105

Earlier quoted context omitted.

malloc() isn't O(1), but allocations in a normal GC are O(1).

Is there some reason that malloc() would be slower asymptotically than a GC? Why couldn't whatever technique is used for the fast GC be used for malloc() as well?

malloc implementations often involve some kind of a search to find a free area that can satisfy the request. See http://www.gii.upv.es/tlsf/ for an O(1) implementation - use a large number of free lists, one per size, using bit scan instructions on the block size to select the list to use. To malloc, grab the first entry, and put any remaining portion on the appropriate free list.

To free, add the block to the appropriate free list. Assume blocks participate in a doubly-linked list of all blocks, used and free alike, in address order - adjacent free blocks can be coalesced at this point.

Re: Why databases use ordered indexes but programming uses hash tables

#163

Post by mrfusion »

geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Why can’t hash tables shrink and grow gracefully?

Re: Why databases use ordered indexes but programming uses hash tables

#164

Post by ithkuil »

cesarb wrote: post #153
cperciva wrote: post #37

Earlier quoted context omitted.

On modern hardware a key lookup in a hash table isn't necessarily a single page read! Sure, it's a single virtual memory access, but if that page isn't in your TLB you need to read the page table... and if the page containing that part of the page table isn't in the TLB you need to read that page... On modern hardware, every memory access looks very much like a B-tree lookup.

> and if the page containing that part of the page table isn't in the TLB you need to read that page... I thought page tables used physical addresses, which are accessed directly without any TLB lookup (except when nested paging during virtualization, which adds another level of indirection). Of course, the processor still needs to read each level into the data cache(s) while doing a page table walk.

Page tables can have multiple levels. For example in x86_64 you'd have 4 levels, i.e the virtual->physical mapping is implemented as a tree with depth 4, where each leave and internal node of such tree is 4kb (page size). (As usual, details are more complicated than that)

Re: Why databases use ordered indexes but programming uses hash tables

#165

Post by jameshart »

mrfusion wrote: post #163
geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Why can’t hash tables shrink and grow gracefully?

Because items are placed into buckets based on their hash, and as you add or remove buckets you need to redistribute items.

I guess it depends what your definition is of ‘graceful’.

Re: Why databases use ordered indexes but programming uses hash tables

#166

Post by MiroF »

cperciva wrote: post #37
geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

On modern hardware a key lookup in a hash table isn't necessarily a single page read! Sure, it's a single virtual memory access, but if that page isn't in your TLB you need to read the page table... and if the page containing that part of the page table isn't in the TLB you need to read that page... On modern hardware, every memory access looks very much like a B-tree lookup.

This is not how TLB lookup works

Re: Why databases use ordered indexes but programming uses hash tables

#167

Post by cesarb »

ithkuil wrote: post #164
cesarb wrote: post #153

Earlier quoted context omitted.

> and if the page containing that part of the page table isn't in the TLB you need to read that page... I thought page tables used physical addresses, which are accessed directly without any TLB lookup (except when nested paging during virtualization, which adds another level of indirection). Of course, the processor still needs to read each level into the data cache(s) while doing a page table walk.

Page tables can have multiple levels. For example in x86_64 you'd have 4 levels, i.e the virtual->physical mapping is implemented as a tree with depth 4, where each leave and internal node of such tree is 4kb (page size). (As usual, details are more complicated than that)

Yes, and each level of the tree has the physical address of the next level, so no TLB lookup is necessary (the top of the tree, in the TTBRn or equivalent registers, is also a physical address).

Re: Why databases use ordered indexes but programming uses hash tables

#168

Post by ithkuil »

cesarb wrote: post #167
ithkuil wrote: post #164

Earlier quoted context omitted.

Page tables can have multiple levels. For example in x86_64 you'd have 4 levels, i.e the virtual->physical mapping is implemented as a tree with depth 4, where each leave and internal node of such tree is 4kb (page size). (As usual, details are more complicated than that)

Yes, and each level of the tree has the physical address of the next level, so no TLB lookup is necessary (the top of the tree, in the TTBRn or equivalent registers, is also a physical address).

oh yeah, I totally misread the comment: a page fetch is required, but that has nothing to do with the TLB indeed

Re: Why databases use ordered indexes but programming uses hash tables

#169

Post by tanilama »

mrfusion wrote: post #163
geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Why can’t hash tables shrink and grow gracefully?

It might be down to memory/space allocation after all.

All hashtable requires rehashing up to certain fill rate, otherwise it will regress to linear look up. For the two most popular implementations, linked-list based or open addressing based, the common strategy for rehashing is to create another instance of hash table and copy the KV over. But on disk, this will be disastrous.

Post reply on HN