Author Archives: mischasan

About mischasan

I've had the privilege to work in a field where abstract thinking has concrete value. That applies at the macro level --- optimizing actions on terabyte database --- or the micro level --- fast parallel string searches in memory. You can find my documents on production-system radix sort (NOT just for academics!) and some neat little tricks for developers, on my blog My e-mail sig (since 1976): Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection.

Hunting the wily #if

Since a reader (djmott) found some use for Stupid gcc trick #2: finding all included files, recursively …  here’s another quick trick for finding which set of nested #ifdef/#elif/… controls the inclusion/exclusion of some piece of your source file. This … Continue reading

Posted in Uncategorized | Leave a comment

Why is Quicksort that quick?

Quicksort has a reputation for speed. In school, you learn that it is O(n log n) … the optimum for all single-threaded, comparison-based sorts. In fact, when combined with median-of-three pivot selection, tiny-partition insertion-sort, and special equal-keys handling (qv Top … Continue reading

Posted in algorithm, sort, Uncategorized | Leave a comment

Bug fix for ACISM

Several people have used the Aho-Corasick interleaved state-transition matrix code, only to find it didn’t match all strings (!) The bug was in the machine construction: the “prune backlinks” step in acism_create is (as-is) broken. I commented it out, and … Continue reading

Posted in aho-corasick, algorithm, string search | Leave a comment

GMAKE cheap trick #4 for non-recursive make

One of the tedious sides of non-recursive make is that all makefiles share the same namespace. Every variable or pseudo-target name must be unique across all subprojects, or must be a well-known global variable/target, to which a subproject’s bits and … Continue reading

Posted in make, non-recursive make | Leave a comment

GMAKE cheap trick #3

What’s the shortest way to define a GMAKE var that is exactly one space? SPACE = $~ #

Posted in make, Uncategorized | Leave a comment

Quick update on ACISM

Thanks to Nicholas Sinnott-Armstrong, who suggested that the fast and compact Aho-Corasick interleaved state machine, on github could use an upgrade from 32-bit to 64-bit, to handle (say) over 40M strings — a bit beyond 32-bit ACISM’s 16MB limit. He … Continue reading

Posted in Uncategorized | 3 Comments

21st Century Programming Languages

When I was a co-op student, I programmed in a language that had lambdas, currying, user-defined operators (including assignment), dynamic compilation, and a wealth of other features. It was neat, efficient and readable. That languages was POP-2. It was written … Continue reading

Posted in Uncategorized | Tagged , | Leave a comment