From Newsgroup: comp.misc
Scott Dorsey wrote:
Yes.
The optimist sees an glass half-full
The pessimist sees a glass half-empty
The engineer sees a 50% safety margin against overflow.
Or, the container is twice as big as it needs to be.
I will say that the way math is taught in engineering programs is completely different than the way it's taught in math programs. My freshman calculus classes were all about being able to do derivatives and integrals as quickly as possible in closed form... there were no proofs and few explanations,
just memorization of methods, and as many methods as possible given the time allowed. When I went to EE grad school I was glad of this but it was not pleasant to learn.
Yes, it was completely different from that for me in grad school. Not at
all memorization, class, day after day was long proofs of stochastic principles scrawling across three chalkboards.
What I'm facing right now is a growing pile of projects that are
mathematical modeling of program input, queries, and manipulations.
The problem is that there are time caps. From what I can tell, it is prohibitive often of explicit modeling of the operation in an array or whatever. For example, if the operations of a sort are to be conveyed,
it will be too time consuming to store the array, sort the array
according to the apropos sort (be it insertion or adjacency sort), and annotate it while that sort is taking place.
If the meat is cut out, the explicit internal sorting of the array, I
believe it will be sufficiently expedient.
Whatever you can say, actually moving those elements around is probably
a big waste of time, because that's not what the program needs to do. It
only needs to list the positions that are moved. This extends to a great number of projects in my back load.
Put simply,
When an input string of parentheses becomes so massive that the raw read/ingestion time of the string itself is the primary bottleneck, traditional linear algorithms (like a sequential single-threaded stack)
hit a wall. If your data is gigabytes or terabytes long, a single CPU
core reading character-by-character cannot scale.-aTo manipulate and
validate parenthesis strings when the input size is the limiting factor, computer scientists shift away from simple stacks toward architecture
built for parallelism, SIMD acceleration, hardware-native streaming, and algebraic properties.-a1. Parallel and MapReduce Processing (The Monoid Approach)To process massive inputs across multiple CPU cores or
distributed machines, you cannot use a normal stack because a stack
requires knowing everything that came before it. Instead, the problem is treated as an algebraic monoid.-aHacker NewsThe Concept: Any chunk of parentheses can be reduced down to a simple pair of numbers: (unmatched_closed, unmatched_open). For example, the slice )))()(((
reduces to (2, 3) because the inner () cancels out, leaving 2 unmatched closers and 3 unmatched openers.-aWhy it works for huge data: This
reduction operation is associative. You can split a 10-gigabyte file
into 100 separate 100-megabyte chunks. 100 different threads or machines
can scan their chunks entirely independently in parallel.-aThe Merge
step: Once each thread computes its local (closed, open) pair, a master
thread merges those pairs using a simple formula:\[\text{Merged\ unmatched\_closed}=c_{1}+\max (0,c_{2}-o_{1})\]\[\text{Merged\ unmatched\_open}=o_{2}+\max (0,o_{1}-c_{2})\]Because the merge step
takes \(O(1)\) constant time, the overall runtime scales strictly with
how fast your hardware can split and stream the raw bytes in
parallel.-a2. SIMD Acceleration (Vectorization)When a single machine
needs to parse data at the absolute limit of memory bandwidth (e.g.,
dozens of gigabytes per second), it uses SIMD (Single Instruction,
Multiple Data) instructions supported by modern CPUs (like Intel's
AVX-512 or ARM's Neon).-aHow it beats the bottleneck: Instead of a loop inspecting one byte at a time, SIMD registers can load 32 or 64
characters at once into a single vector pipeline.-aThe Bitmask Trick: The
CPU executes a vector comparison to instantly create a bitmask of where
the ( and ) are. Using population count (popcount) and bitwise shifts,
the hardware computes the prefix sums of the nested depths for 64
characters simultaneously in a fraction of a CPU cycle. This technique bypasses traditional branch instructions entirely, preventing CPU branch mispredictionsrCowhich are usually a massive penalty when parsing random
data streams.-a3. Tree-Structured Parentheses Manipulation (Finger Trees
& Rope Data Structures)If the goal is not just checking if they match,
but actively manipulating them (e.g., cutting a 1 GB chunk out of the
middle, pasting it elsewhere, and checking if it's still valid),
re-scanning the string would be disastrous.-aRopes / 2-3 Finger Trees:
Rather than a flat array or string, the parenthesis sequence is stored
as a balanced tree where the leaf nodes contain segments of the
text.Augmented Metadata: Each internal node in the tree stores the
aggregated (unmatched_closed, unmatched_open) monoid value of its
children.The Payoff: If you insert or delete text, you only need to
update the nodes along the path from the leaf to the root (\(O(\log N)\) time). The tree instantly recalculates whether the entire multi-gigabyte document remains balanced without ever touching 99.9% of the actual characters.-a4. Hardware-Level Streaming (Memory-Mapped Files &
Zero-Copy)When input size is the limiting factor, standard I/O overhead (copying data from the hard drive to kernel space, then to user space,
then parsing it) will kill performance before an algorithm even starts.-aMemory-Mapped Files (mmap): The system maps the massive file
directly into the processrCOs virtual memory space. The OS pages the data directly from the disk cache straight into the CPU caches as
needed.Zero-Copy Parsing: The algorithms operate directly on the
byte-stream pointer provided by mmap. No strings are allocated, no sub-segments are copied, and no memory overhead is spent. The
performance curve aligns perfectly with the physical sequential read
speed of the underlying NVMe SSD or network storage.
--
Everything I fight for leaves a bitter taste
Everything I cry for laughs into my face
Everything I scream for barely knows my name
Everything I'd die for will die just the same
--- Synchronet 3.22a-Linux NewsLink 1.2