You are not logged in.

sprezzatech blog #0018

Dirty South Supercomputers and Waffles
UNIX, HPC, cyberwarfare, and chasing perf in Atlanta.

SprezzOS Weeklyish Oblations, Objections, and News (SWOON) Vol. 1 Issue 6.
Tue Apr 23 14:43:11 EDT 2013

SprezzOS Weeklyish Oblations, Objections, and News (SWOON)

Volume I, Issue 6. 2013-04-23. Editor: Nick Black.



I. INTRODUCTORY RITES

“The views of space and time which I wish to lay before you have sprung from the soil of experimental physics, and therein lies their strength. They are radical. Henceforth space by itself, and time by itself, are doomed to fade away into mere shadows, and only a kind of union of the two will preserve an independent reality.”

—Hermann Minkowski, Raum und Zeit (1909)


Exciting times! Sorry about SWOON dipping out for a minute there, though you can expect this to happen from time to time. Don't let this imply that nothing was going on in the People's Commonwealth of SprezzOS. On the contrary, it's during precisely the busiest flurries of activity that SWOON gets pushed down the stack. I've started filling in the FAQ section of the SprezzOS Handbook; they are most informative.

I declared war on crappy APT performance with my RAPTORIAL project. Details of the campaign can be found on the Debian development list:
In both cases, I use my libblossom library to detect the processing topology and provide H-tree-based thread spawning (Intel's Thread Building Blocks (libtbb) would have been another possible solution). We never want more computational threads than we have virtual processing elements, so we use libblossom's blossom_per_pe(3) to spawn one thread for each processor. The H-tree accomplishes this in work O(N) and height O(lg2N)). The easiest parallelism to extract is that of multiple files within a directory. readdir_r(2) provides us with a natural (i.e., kernel-enforced) synchronization point, and our blossom begins marching through the directory.
RAPTORIAL logo
Take it right into the danger zone.
Unfortunately, these files tend to have wildly different lenghths (two to three orders of magnitude as compressed on disk, three to four orders of magnitude as uncompressed to memory), so we need also extract parallelism within a file.

Libblossom, however, doesn't allow multilevel blooms. If each file's thread were to spawn O(N) copies of itself, we'd have O(N²) threads on O(N) processing elements, and when you have exponentially more threads than cores you're gonna have a Bad Time. So we can't just call blossom_per_pe(3) again. Instead, the solution is to schedule neither files nor chunks but chunk-files (and now you can see the relevance of this SWOON's epigram). I've done this in raptorial-file(1), RAPTORIAL's optimized apt-file(1) clone, and as you can see in message #420 above, with this technique we manage to keep the processors reasonably busy. I've not yet done this in rapt-show-versions(1), as it's already tremendously faster than apt-show-versions(1) and doesn't need much more parallelism on, say, my HyperThreaded quad-core. I'll do it sometime soon, though, for completion (rapt-show-versions(1) is instead simply parallelizing on files, and lexing each one in serial, some “breadth-first parallelism” if you will). This design is analyzed at length in message #409 above.

As for our actual pattern matching, nothing too fancy; we do an “Advanced” Aho-Corasick automaton (AC + σ-function ⇒ AAC), and special-case single pattern searches with Boyer-Moore-Galil (the G of BMG is Zvi Galil (צבי גליל‎), the sui generis Dean of GT's College of Computing. See the picture at the end of this section. ATL, baby, ATL!). Pretty standard shit. Enough talk! Behold the awesome power of Georgia Tech Computer Science! (by which I do not refer to these ugly-ass graphs):

raptorial-file vs apt-file
Pwnage (note truncation for #2, 'a').
rapt-show-versions vs. apt-show-versions
Cruel and unusual pwnage.


This won us some nice press coverage from Phoronix (the best site for general Linux news on the web, w00t!) and Italy's TuxJournal. CENTRAL EUROPEAN DOMINANCE. The dirty hippies up in Colorado's LWN still have yet to give us any love—I suspect they disbelieve that anything smart or good or even literate can emerge from the Deep South, but we'll make believers of them yet.

Speaking of press coverage, we're now enshrined in the Crappy Design subreddit. I will wear this like a perverse badge of honor, because what's even worse than crappy design is being a designer. This was unexpected and wacky and kind of fun, but I'd prefer to be getting attention for more meaningful accomplishments.

two generations of hax0rs
Your Humble Editor, a computing legend, the Ramblin' Wrek, some people I don't know, and TOO MUCH DAYSTAR.


Κύριε, ἐλέησον.



II. LITURGY OF THE WORD


Awwww shit, we've got, what, a month of updates here? This list is neither autoritative nor exhaustive, nowhere close to that latter actually. Also major updates throughout the sound stack, a few in the OpenGL stack (CEGUI and Ogre, for sure), the OCaml world, the Haskell stack as always, the Ruby stack...this is too boring to continue, but trust me, a veritable metric shitload of package updates. Since the last SWOON (2013-02-22), we've added 482 source packages and 1674 binary packages -- not too shabby a month's work.

Suprisingly(?), we're sticking with kernel 3.7.9 for a minute longer. I've got my reasons.

I'm skipping the rest of this Issue, because there's lots and lots of shit to do. Hack on!

καὶ εἰς ἕνα Κύριον Ἰησοῦν Χριστὸν τὸν υἱὸν τοῦ Θεοῦ τὸν Μονογενῆ.



III. LITURGY OF THE EUCHARIST


Will not be heard today.



Mysterium fidei.



IV. COMMUNION RITE


Will not be heard today.


Agnus Dei, qui tollis peccata mundi, miserere nobis.



V. CONCLUDING RITE

Ite, missa est.


Pimpin' ain't easy...but computers are.

Per ardua ad astra.
SprezzOS logo