181–190 of 205 posts
Because databases are designed to be efficient at scale. A hash table just doesn't have the functionality that a database with a B-tree variant does.
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.
Earlier quoted context omitted.
doesn't this force you to define a comparator for everything though?
As opposed to defining a hash code for everything, yes. Parent asserts that writing obviously-correct comparators is easier.
Java itself introduced Objects.hash(Object...) in 1.7 https://docs.oracle.com/javase/7/docs/api/java/util/Objects....
It's never really been an issue at all to implement equals/hashcode, which you're required to do for effectively all Collections-based usage anyway.
Earlier quoted context omitted.
Oracle forms vs modern web development is a little Off topic but I’ll bite. Could gmail have been built in Oracle forms, how about slack? How about Asana? How about an LMS such as blackboard, moodle, or D2L? Can you name any popular mainstream product that could be built upon and run off the Oracle forms product? Oracle forms will get you 80% of the way there, and the final 20% will be impossible.
> Could gmail have been built in Oracle forms, how about slack? How about Asana? How about an LMS such as blackboard, moodle, or D2L? Can you name any popular mainstream product that could be built upon and run off the Oracle forms product? Yes, it could. Not going to judge whether it's a good idea or not, but it most certainly could be implemented. I suspect you're not aware just how much capability relational datab…
One of the most insightful design docs I ever read was an exploration by an engineer of how GMail 1.0 could have been implemented with commodity tech and how it'd compare cost wise. The rather sobering conclusion was that it'd have similar functionality and been cheaper to develop/run.
Earlier quoted context omitted.
Growing hash tables only takes amortized O(1); you just do two operations per logical operation, which is still O(1). One search term is "incremental resizing." https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing
In practical applications, costs are often not amortized. If lucky transactions are more than fast enough but unlucky transactions time out because they perform a rebuild it's a defect that cannot be accepted because average performance is good. Most databases need to take care of worst case performance with techniques that increase complexity and degrade best-case and aggregate performance (e.g. maintaining two hash…
> Some hash table implementations, notably in real-time systems, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. If one cannot avoid dynamic resizing, a solution is to perform the resizing gradually.
[1]: https://en.wikipedia.org/wiki/Hash_table#Alternatives_to_all...
Earlier quoted context omitted.
GCs are typically allowed to (and often do) move objects, while malloc/free do not. This means that malloc/free must maintain data structures tracking allocated vs. free space, while compacting GCs keep all the free space in a single contiguous address space, so allocating an object just increments the "start of free memory" pointer.
Of course, that just moves the cost from the allocation side to the GC side. This means that the GC must maintain data structures tracking the type of each object (to know which fields are references), the root references, and several others (like card tables) for an efficient implementation. For malloc/free, releasing an object can just add it to a free list (a pair of pointer writes), while a compacting GC has to u…
Doing more work but elsewhere can (possibly) make your program faster. GC's often eat more CPU and RAM which hurts when you need more of either. But C/C++ can occasionally put malloc pressure on your critical path hurting you when you have plenty of resources where a GC might actually help you.
If it was any simpler it wouldn't be so damn interesting and fun.
Earlier quoted context omitted.
oh yeah, I totally misread the comment: a page fetch is required, but that has nothing to do with the TLB indeed
what's the difference? "page fetch" is not really something that can be googled on the web.
When the virtual address you're looking to resolve is not present in that cache (i.e. when you have TLB miss), the CPU falls back to walking the page table hierarchy. At each level of the tree, the CPU reads an physical address of the next level of the tree and performs a memory fetch of that page table entry (in my previous comment I erroneously said a "page fetch", but it's actually only performing a cache-line sized fetch) and repeatedly so until it reaches the leaves of the tree which contain the Page Table Entry that contains the physical address of the (4k) physical page associated with the virtual page address you wanted to resolve.
Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…
My favourite example of galactic algorithms is the most efficient way to multiply two numbers. As the Wikipedia page[1] states: An example of a galactic algorithm is the fastest known way to multiply two numbers,[2] which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 21729 digits [1] https://en.wikipedia.org/wiki/Galactic_algorithm
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…
> In a database system, the concern was traditionally to minimize page accesses Is it really about memory access or disk loads?
Though btrees are friendly to cpu caches too, but really it's about minimising disk accesses.
Earlier quoted context omitted.
As opposed to defining a hash code for everything, yes. Parent asserts that writing obviously-correct comparators is easier.
funny enough, a hash code defines an order on a set