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:

• #320 “apt-show-versions rewrite complete” (2013-03-20)
• #409 “apt-file performance characterization” (2013-03-24)
• #420 “apt-file rewrite complete” (2013-03-25)

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(lg₂N)). 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. 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):



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.

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.

• GNOME ⇒ 3.8, with associated Pango ⇒ 1.34.0, Cogl ⇒ 1.14, etc.
• GCC ⇒ 4.8
• QT ⇒ 5.1
• Samba ⇒ 4.0.4
• Clang ⇒ 3.2
• GNU binutils ⇒ 2.23.2
• UNIXODBC ⇒ 2.3.1
• Mosh ⇒ 1.2.4
• tmux ⇒ 1.8
• libbluedevil ⇒ 1.9.3
• X.org input-mouse ⇒ 1.9.0, video-intel ⇒ 2.21.5
  new Nouveau, new modesetting, new input-keyboard...
• libavcodev ⇒ 9.1.3
• FFMPEG ⇒ 1.1.3
• Mesa ⇒ 9.1.1
• libVA ⇒ 1.1.1
• KDE ⇒ 4.10.0
• GStreamer ⇒ 1.0.6
• Boost ⇒ 1.53
• Allegro ⇒ 5.1.5
• Wayland ⇒ 1.0.6
• Cython ⇒ 0.17.3
• MySQL ⇒ 5.5.30
• Harfbuzz ⇒ 0.9.14

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

• The most recent release of SprezzOS is 1.1.0 ("von Neumann").
• There are now 2162 source packages in SprezzOS.
• There are now 8955 binary packages in SprezzOS.
• There were N/A commits to SprezzOS repositories this week.
• There are now 2 registered Sprezzadevs.

Ite, missa est.

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

Per ardua ad astra.