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 perl snippet prefixes each line of a source file with an indicator of which #if/#elif/#else (lines) decided inclusion of the line of interest. Here’s part of “ifdent plat.h | nl “:

 1 +1:#ifndef PLAT_H
...
142 +1+142:#ifdef _MSC_VER
...
177 +1+142+177:# if !defined(getpid)
178 +1+142+177:# define getpid _getpid
179 +1+142:# endif
...
225 +1-142:#else
...
325 +1-142+325:# if !defined(BYTE_ORDER)
326 +1-142+325+326:# if defined(__hpux) || defined(__powerpc) || defined(__sparc)
327 +1-142+325+326:# define BYTE_ORDER BIG_ENDIAN
...
331 +1-142+325+330:# include <endian.h>
332 +1-142+325-330:# else
333 +1-142+325-330:# error BYTE_ORDER not defined
...
366 +1-142+366:# if defined(__darwin)
...
375 +1-142+366+375:# if defined(__x86_64)
376 +1-142+366+375:uint64_t bswap_64(uint64_t x) { asm("bswap %0": "=r"(x):"0"(x)); return x; }
377 +1-142+366-375:# else // i386
378 +1-142+366-375:uint64_t bswap_64(uint64_t n)
...
413 +1-142:# endif
...
1213 :#endif//PLAT_H

And the source for ifdent:

#!/usr/bin/perl -w
use strict;
my $prefix = '';
while (<>) {
    if (m{^#\s*if}) { $prefix .= "+$."; }
    elsif (m{^#\s*elif}) { $prefix =~ s{\d+$}{$.}; }
    elsif (m{^#\s*else}) { $prefix =~ s{\+(\d+)$}{-$1}; }
    elsif (m{^#\s*endif}) { $prefix =~ s{.\d+$}{}; }
    print "$prefix:$_";
}

 

 

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 3 Quicksort optimizations) it is faster than its closest comparison-based competitors: merge sort and heap sort. (That doesn’t apply to near-sorted input, but that’s another story). Timsort makes the best of merge sort, with similar extensions, to cover more edge cases than the above quicksort add-ons.

But it puzzled me that Quicksort was often much faster than, say, a heap-with-hole sort — an optimization of heap sort. Then, a data-oriented-design concept rang a bell: real-world keys are often complex data structures: pointers to key-parts scattered across the heap. Getting all the parts from RAM to cache is a dominating cost. And here are some pertinent features of Quicksort:

• all comparisons are against one (pivot) key. No matter how scattered the pivot key parts are (in RAM) it is guaranteed they are in L1 cache.
• as Quicksort recurses into smaller and smaller partitions, it eventually reaches one small enough that all scattered key parts are in cache. From there on down, every child recursion will be using keys completely in cache. This is repeatedly true as Quicksort works its way down through the sizes of L3/L2/L1 cache, then the bottom-level tiny insertion sorts.

Next up: how radix sort can beat Quicksort on its home (cache) turf, for real-world (complex) keys.

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 voilà it works.
I will update github once I’ve sorted out an SSL cert issue 😛
Thanks for the patience of those who took that code and stumbled on that bug; and special thanks to perfgao@gmail.com, who came up with the tiny example that identified the problem.

FWIW the prune-backlinks code will return; but it will check that the subtrees of targets of backlinks, not just the immediate children, must be a subset of the subtree of the source, in order to prune the link.

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 pieces are appended. Appending to global variables doesn’t alway have the desired effect, either.

For example, these kinds of rules/assignments work (assuming EXPORT_PGMS is used and owned by global_rules.mk):

include global_rules.mk
EXPORT_PGMS += rsaencrypt
RSAENCRYPT_testfiles = foo.dat bar.dat

all : rsaencrypt
clean .PHONY: rsaencrypt.clean
rsaencrypt.clean :; rm -f ${RSAENCRYPT_testfiles }

But these do not:

CFLAGS = -g # problem: previous CFLAGS wiped out
CFLAGS += -Imock # oops: now ALL subprojects see this flag
clean:; rm -f test.out # fails; "clean:" actions can only be defined once
clean::; rm -f test.out # fails if "clean:" is defined anywhere.

A second tedious side is that the current working directory will not be the one where the Makefile and source files live. That means that every file reference must have a directory path. The obvious change makes the makefile harder to read, and hence more prone to mistakes …

rsaencrypt.source = ${rsaencrypt}/alpha.c ${rsaencrypt}/beta.c ${rsaencrypt}/gamma.c \
                    ${rsaencrypt}/delta.c ${rsaencrypt}/beta.c ${rsaencrypt}/epsilon.c \
                    ${rsaencrypt}/digamma.c 

One approach is:

rsaencrypt.source = alpha.c beta.c gamma.c delta.c epsilons.c digamma.c
rsaencrypt_source.zip : ${rsaencrypt.source:%=${mydir}/%}
# ... or without the extra variable:
rsaencrypt_source.zip : $(addprefix ${rsaencrypt}/, alpha.c beta.c gamma.c delta.c epsilons.c digamma.c)

However, there’s a little abbreviation trick that can help. All of my makefiles begin like this:

~ := rsaencrypt
. := $(word 1,${$_} .)

There’s nothing special about the choice of characters; any of $! $+ $- $, $` $_ will also work. The object is to have an unobtrusive single-character abbreviation, avoiding letters, digits and gmake’s own $@ $< $^ $* : = # .

The $(word...) expression sets $. to . if no parent makefile has set ${rsaencrypt}. Long variable names that are just following cross-project conventions can be prefixed with “$~…”:

$~source = $./alpha.c $./beta.c $./gamma.c $./delta.c $./epsilons.c $./digamma.c
$~source.zip : ${$~source}

Note the :=, not =. That means that, as sub-makefiles are included, the definitions of $~ and $. change from that point on. Which also means that include ${subdir}/submakefile lines must come at the bottom of the makefile, and successive include directives can’t use $. for the pathname. Well, nothing’s perfec. 🙂

GMAKE cheap trick #3

What’s the shortest way to define a GMAKE var that is exactly one space?

SPACE = $~ #


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 tried doing that, and with a small performance tweak, I’ve updated github. The state machine is twice as large, of course. On a 64-bit processor, it should be a couple cycles faster, though, because the shifts and masks are now constants. Anybody else using ACISM for pattern sets that large ??

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 in 1970.

“Unusual uses of SSE2” posted to github

In this month’s frenzy of putting source code out there in a usable form, I’ve posted source to github for the SSE2 implementations of string search, BNDM search, sorting [16] doubles, and bit-matrix transpose; plus some convenience tools for SSE2.
http://github.com/mischasan/sse2

A tiny asynchronous DNS client posted to github

There’s a world out there beyond the “bind” daemon … and this DNS client library can access it and show you how it works. This is my reference model for writing a tiny independent library plugin to another event-loop mainline, without callbacks. and without compromises. It also has a few good tricks for using a hash table as a cache — deletion by TTL is incremental. https://github.com/mischasan/madns

HXFILE source posted to github

In case you’ve read my paper on highly-concurrent linear hash files, and want to see/use the source, I’ve posted it to https://github.com/mischasan/hx. It’s been a lot of fun, and I’ve used it in an OLAP product and some performant key-value lookup apps. As-is, it is limited to 128TB per file and 32K per record.