so becausse the 1978 pohlig-hellman paper mentioned that one of knuth's taocp books had the sunzi remainder theorem they used, i finally cracked and opened up the knuth 1998 sorting and searching text
46
Replies
0
Boosts
immediately i can see that knuth's style must have inspired the lovely approach in DH 1976 where they spend the entire time shouting out papers they love and giving deep, thorough citations to people who have solved some problem or other. so that's kind of nice, even though knuth (in the 1998 book especially) spends a great deal of time thinking about how to perform large-scale surveillance, and also daps up ron rivest way too frequently
there are a lot of ways he introduces to describe hashing that are thoroughly aligned with the ways i have been thinking about it in my head. so i feel pretty confident now just doing my own bullshit data structures. [recall that i define "hash" to mean "hash table" and not "checksum"]
however, there is an immense reliance on "expected-time" analysis, which i can immediately see led to linux's i/o bullshit directly:
Perhaps the reader has been skeptical of B-trees because the degree of the root can be as low as 2. Why should we waste a whole disk access on merely a 2-way decision?! A simple buffering scheme, called least-recently-used page replacement, overcomes this objection; we can keep several bufferloads of information in the internal memory, so that input commands can be avoided when the corresponding page is already present. Under this scheme, the algorithms for searching or insertion issue “virtual read” commands that are translated into actual input instructions only when the necessary page is not in memory; a subsequent “release” command is issued when the buffer has been read and possibly modified by the algorithm. When an actual read is required, the buffer that has least recently been released is chosen; we write out that buffer, if its
contents have changed since they were read in, then we read the desired page into the chosen buffer.
literally EVERY SINGLE OS JUST DOES THIS EXACT SHIT TO THE LETTER AND DOESN'T THINK TWICE! it's FUCKED!
Since the number of levels in the tree is generally small compared to the number of buffers, this paging scheme will ensure that the root page is always present in memory; and if the root has only 2 or 3 children, the first-level pages will almost surely stay there too. Any pages that might need to be split during an insertion are automatically present in memory when they are needed, because they will be remembered from the immediately preceding search.
"the first-level pages will almost surely stay there too" this is not a serious analysis bro you've been riding people's coattails for way too long!!!!
however, completely by chance, i did find this paper from a team led by rui-Xiang ma from wuhan national laboratory for optoelectronics (https://sci-hub.st/10.1007/s11390-021-1247-6) which describes a database in persistent memory that works incredibly closely to my fractal zip file approach, with particular attention to data consistency and write optimization. so i can totally just steal this for anything i haven't figured out yet for the filesystem shit
however, completely by chance, i did find this paper from a team led by rui-Xiang ma from wuhan national laboratory for optoelectronics (https://sci-hub.st/10.1007/s11390-021-1247-6) which describes a database in persistent memory that works incredibly closely to my fractal zip file approach, with particular attention to data consistency and write optimization. so i can totally just steal this for anything i haven't figured out yet for the filesystem shit
especially after going through the btrfs source code yesterday i basically think i can make a filesystem like so much more expediently than i had previously planned. it's really not hard if you design it upfront instead of half-assing everything all the time
i also followed on an "SB-tree" mentioned by knuth that sounded close to what i wanted: https://sci-hub.st/storage/2024/634/00406abfc8d251b45eb6227c1f995db7/10.1007@BF01185680.pdf and while i still think a global tree organization is obviously fucked, it does a lot of things really thoughtfully:
(4) The high performance characteristics of an SB-tree are much less subject to degradation than traditional B-tree structures when the tree is modified to accommodate changing information. For this reason, it is appropriate for situations where regular B-tree reorganization cannot easily be performed.
but i really really liked the ACTUAL FUCKING SEMANTICS OF DATA MODIFICATIONS described for fucking ONCE:
(7) We draw an analogy between the K nodes of a multi-page block and the entries of a B-tree node: an analogous policy of "block-splits", "block-merges" and "block-borrows" is pursued
then he calls out the half-assed "expected time" analysis used for B/+ trees:
It is well known that the root node is usually found in memory buffers, but this is not the whole story. We offer the following rough analysis to estimate the "Effective Depth",
D_E, of the B+-tree, which we define as the expected number of pages not found in memory buffers during a search from the root to the leaf for an entry with a random key value.
It is interesting to note that the graph of Fig. 3 presents a scalloped appearance. This indicates that increasing the ratio of memory buffer size to B+-tree size has an important effect in certain ranges, where a large proportion of a B-tree level can be contained in memory, but that this effect is of diminished importance in other ranges, where the proportion of the level contained becomes less useful in saving real I/Os.
SAVE THE REAL I/OS!!
they SB-tree paper also goes way way out of its way to shout out a completely different paper describing a "BD-tree" ("bounded decision") data structure, just because they really like it???? so wholesome!!!!
The common uses of merge join and ordered user display seem to require the more difficult key sequential access, although Lomet points out that for many uses. "By changing algorithms, it is frequently possible to use the results of a range search, without the extra cost of putting the records in key order." To support key sequential access, BD file records within each bucket are maintained in key order. Since records are ordered from one node to another, a total ordering can be achieved by performing a "merge" on the ordered sequences from the different buckets of a node, as in the final stage of a multi-merge sort. This is best effected by using a "heap" structure on the smallest keys in each bucket, successively removing the minimum, inserting the next in that bucket, and reorganizing the heap; each such heap reorganization takes log_2 k steps, where k is the number of buckets.
basically the moral of all of the good papers is: don't rely on one single algorithm or data structure to generally work fine across every possible use case! develop algorithms and data structures tuned to each potential query and input distribution you expect to have to handle!!
For very large files, where the effective depth of an SB-tree becomes significantly greater than one, the guarantee to keep all of the directory level of the BD tree in memory is an important advantage.
this is in fact what a good paper looks like. you can in fact gas yourself up and other good work at the same time!
The CPU cost as each entry is generated is what is needed to remove the minimum of a heap, advance
the relevant bucket cursor, and insert the next entry under the cursor back into the heap. We represent this asCPU_{heap}, a cost which is logarithmic in
the number of buckets in the node.
this analysis also makes sure to both specify as well as clearly differentiate CPU and memory requirements to perform specific operations (they're obv related, because the CPU needs to pull memory into the cache, but when describing them separately (and asymptotically) you end up producing an analysis that covers attempts to try to "be clever" or "cheat" (like i do when i introduce i/o transactions on top of POSIX so applications can simply wait until the filesystem reconciles their shared state before returning from the blocking syscall)
YES!!!!!
In spite of this, it would seem that an ideal SB-tree implementation would permit a user choice as to the number of nodes in a reorganization, up to a reasonable limit such as the minimum number on a block. The parameter is not particularly hard for the file manager to supply, and in designing the access method we should try not to prejudge the relative frequency of range-retrievals in comparison to updates.
FIRST TIME IN WORLD HISTORY THAT A FILESYSTEM DESIGNER HAS PROPAGATED A PERFORMANCE-CRITICAL INPUT-SENSITIVE JUDGEMENT TO THE MOTHERFUCKING APPLICATION LAYER!!!
As time passes, even less activity will be necessary to justify this buffer size. Note that for many years the economic use of IBM memory was artificially
constrained by a 16 megabyte virtual memory limit, and users who do not have XA systems are still constrained in that way. This may serve to explain the statement in [11] to the effect that 4M bytes for buffers was not feasible.
Eight Megabytes And Constantly Swapping
A key consideration in memory buffering is whether we need to keep more than one size of buffer: single page buffers for page-nodes and larger sizes for multi-page blocks. It is a common property of modern computer systems that a multi-page read may be accomplished in a scatter/gather form to several non-contiguous memory locations
see i wish i had heard this when i began parallelizing zip file extraction and couldn't find a single example or any mention on the entire internet of anyone trying to do a scatter/gather on the archive format that tells you where everything is laid out in advance!
oh YES!! https://sci-hub.st/10.1007/BF00289145
Unsafe Operations in B-trees
Bin Zhang and Meichun Hsu (1989)
THE GLOVES ARE COMING OFF!!!
A simple mathematical model for analyzing the dynamics of a B-tree node is presented.
you would not BELIEVE how uncommon this sort of very basic analysis is across the database and filesystem literature from the past half-century
We call split, merge, borrow and balance operations unsafe operations in this paper.
in particular, these operations induce (global) contention, which reduces throughput
oh HELL fucking yes!!!!! they are actually describing the data structure under an ordered (linearizable) sequence of mutation operations!!!!
