fairland: Nicer & much faster replacement for next_vector()
authorMarkus Armbruster <armbru@pond.sub.org>
Sat, 25 Jul 2020 12:08:38 +0000 (14:08 +0200)
committerMarkus Armbruster <armbru@pond.sub.org>
Tue, 5 Jan 2021 09:41:36 +0000 (10:41 +0100)
commitd4dcfeec548b124f7628d06fcc3434957ace72e2
treec00c4adb68a9d052318fd243f40d51e892cf3a30
parent68375704b8dcc995ac1457dd868570c3e6f71100
fairland: Nicer & much faster replacement for next_vector()

next_vector() is kind of cute, but it is also unobvious, cumbersome to
use, and slow for arguments greater than one.

Replace it by hexagon_first(), hexagon_next().  The new code takes
O(1) time, whereas the old code takes O(n).  Iterating over a hexagon
changes from

       for (i = 0; i < n; ++i)
           vector[i] = 0;
       do {
           x = x0;
           y = y0;
           for (i = 0; i < n; ++i) {
               x = new_x(x + dirx[vector[i]]);
               y = new_y(y + diry[vector[i]]);
           }
   do stuff with @x, @y...
       } while (next_vector(n));

to

       hexagon_first(&hexit, x0, y0, n, &x, &y);
       do {
   do stuff with @x, @y...
       } while (hexagon_next(&hexit, &x, &y));

In my measurements, it's ~8% slower for n == 1, 25% faster for n == 2,
and more than three times faster for n == 6.

fairland's performance is dominated by it.  Creating worlds for the
Common Fever blitz (distance arguments 3 and 2) and the Hvy Fever
Blitz (distance arguments 6 and 3) on my machine speeds up by a factor
of 1.6 and 2.1, respectively.

Of course, fairland performance is hardly an issue on today's
machines: it takes fairly impractical setups to push run time over a
second.

Signed-off-by: Markus Armbruster <armbru@pond.sub.org>
src/util/fairland.c