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
15
Replies
4
Boosts
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
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!!!!
you don't even need to use latex or any special math notation for this kind of thing. you just need to state out loud:
- these are the mutation operations for my data structure
- this is how we will ensure a strict ordering of operations (linearizability)
- this how the size/complexity/computational effort over the whole sequence of operations will be analyzed
- [if you're lucky] this is how we minimize that work for a given input distribution
linearizability is actually a very strong requirement and may be too strong for some specific subproblems. e.g. for my ring buffer that does every possible variant of structured pairwise blocking/signalling scenarios (or telling the other end when we're waiting for them to hurry up), the codification of forward progress is maintained by the invariants of the ring buffer (data is always in order), so we can do some spinning along with the c11 weak memory model for atomic operations to avoid full "linearizability" by globally locking the whole buffer at once
but we do still achieve linearizability over the data flow through the ring buffer, even if we can improve performance by relaxing the requirement to make each process interaction with the ring buffer linearizable
for my write() calls, i'm actually requiring that any write() performed from within a process on the same file handle within the same i/o sync domain (e.g. multiple threads writing to the same file handle) must have the semantics of a process-global lock to achieve in-process linearizability.
for data striping where you actively want to modify more than one region of the file at a tiime, i'm planning to extend the POSIX {,p}writev() concept and enable vectored write_striped() calls to describe a general bipartite graph that maps a sequence of iovecs to a file offset to write the vectored data at.
the write_striped() call could itself receive (a sequence of (a sequence of (iovecs) mapped to a write offset)), such that when the blocking syscall returns, the modifications to the file data corresponding exactly to what would occur if each [iovec] => offset was processed serially (linearizably)
it's still very much possible for the implementor of such a write_striped() call to identify opportunities for write parallelism where the inputs are disjoint. but the point is that linearizability is so important that even for extremely high performance scenarios you should be able to accept global lock semantics with more thoughtful API design, and only in extremely narrow cases like the ring buffer (which took me several months to design and implement) is it safe to move beyond that strict linearizability requirement
and as mentioned above, the ring buffer itself only works coherently because the result of any asynchronous operation will necessarily, provably achieve linearizability over the data flow through the ring buffer
i said that already but it's really important to emphasize how the analysis of correctness and performance becomes much simpler to understand and easier to create for your own programs if you focus less on "what operations does the CPU do" and more "what data exists in the system and how does it move between states over the course of the system's operation?"
now i'm reading this https://www.cs.utexas.edu/~dsb/cs386d/Readings/ConcurrencyControl/Lehman-Yao.pdf
Efficient Locking for Concurrent Operations on B-Trees
Lehman and Yao (1981)
promising!!!
2. THE STORAGE MODEL
We consider the database to be stored on some secondary storage device (hereinafter referred to as the “disk”). Many processes are allowed to operate on these data simultaneously.
you will not BELIEVE what happens next:
Each process can examine or modify data only by reading those data from the disk into its private primary store (the “memory”). To alter data on the disk, the process must write the data to the disk from its memory.
THAT'S RIGHT!!!!
- PROCESS-LOCAL I/O STATE!!!
- EXPLICIT TRANSFER TO GLOBAL VISIBILITY!!!!
- SEPARATION OF "WRITE" VS "PERSIST" OPERATIONS!!!!!!
The disk is partitioned into sections of a fixed size“ (physical pages; in this paper, these will correspond to logical nodes of the tree). These are the only units that can be read or written by a process.
DENORMALIZED REPRESENTATION OF DATA INTO INDIVIDUALLY-INDEXED BLOCKS!!! SUDDENLY WE CAN ANALYZE THE PATH OF A SINGLE WRITE FROM START TO FINISH!!!
Further, a process is considered to have a fixed amount of primary memory at its disposal, and can therefore only examine a fixed number of pages simultaneously. This primary memory is not shared with other processes.
i have LITERALLY never heard anyone else attempt to codify concurrency control for a filesystem like this before. it's literally so fucking simple!!!!
Finally, a process is allowed to lock and unlock a disk page. This lock gives that process exclusive modification rights to that page; also, a process must have a page locked in order to modify that page. Only one process may hold the lock for a given page at any time. Locks do not prevent other processes from reading the locked page.
you may recall that linux experiences a load of problems with this locking mechanism https://www.kernel.org/doc/html/latest/core-api/pin_user_pages.html#folio-maybe-dma-pinned-the-whole-point-of-pinning
but that's linux in 2026. this paper is from 1981 and they're not mediating between driver-level DMA and applications pinning a page in userspace without knowing it just by issuing a write() call like linux is.
verdict: good! a lock is exactly the right thing to do for this paper
We assume that some locking discipline is imposed on lock requests, for example, a FIFO discipline or locking administration by a supervisory process.
POSIX literally has zero semantics defined for the ordering of write()s to the same file, other than "it is atomic", which means both that:
- writes are never torn
- the data from a
write()must be made visible to the entire system globally before the blockingwrite()call returns
there's certainly no conception of locking, ordering, or queueing!
i also really want to shout out this exciting and intriguing proposal in the final clause of that assumption:
or locking administration by a supervisory process.
this is exactly why i'm so gung-ho about structuring IPC in terms of an interaction graph, and because i think a supervisor process is also the correct, safe, and performant way to do task scheduling!
there are so many different performance scenarios that the userspace application developer can and should be emplowered to describe purely in local terms--the concept of managing "nice" values for build processes in order to ensure the web browser doesn't keep stealing cycles from it is absurd!
in fact, it's perfectly coherent to have each recursive supervisor process describe task scheduling mechanics only between its own processes and no one else's. that in fact makes it super easy for the kernel to implement timesharing by allocating time slices to the entire structured subgraph!
think of it like linux namespaces (i.e. containers)--but instead of retroactively figuring out the mapping from each process to its namespace, then calculating some sort of "quota" (while essentially retaining the global round-robin scheduler),
instead we codify being scheduled on the CPU as not only a privileged operation, but indeed a crucial security boundary in which each supervisor process becomes accountable for how much time it allocates across the subprocesses it spawns
in the kernel, we could even just do "round robin" again--but iterating over strictly nonoverlapping process groups!
this sounds really basic, but what it means is that we don't experience the awful i/o contention that linux does--because all processes blocking on each other's output can be stopped and started at once!
