XS beats Pure Perl

Someone reported some test failures trying to install Tickit, which seemed to be related to shortcomings in Text::CharWidth. The latter seems to have very poor unit test coverage on itself, so the failures didn't appear during its installation, only when Tickit::Utils was tested against it. On initial inspection I wondered if Text::CharWidth simply wasn't using wcswidth(3) correctly, and whether I should get around to my plan of rewriting bits of Tickit::Utils in XS instead for performance, as well as work around this bug.

This turned out to be quite a good idea. Implementing cols2chars() and chars2cols() in XS instead of Perl makes them at least 10 times faster. I tested it on four strings; two ASCII and two Unicode; a long and a short of each:

Calls/sec		PP	XS	Ratio
chars2cols	along	48685	406504	834.97%
chars2cols	ashort	72674	704225	969.02%
chars2cols	ulong	37341	387596	1037.99%
chars2cols	ushort	52966	714285	1348.57%
cols2chars	along	16350	403255	2466.39%
cols2chars	ashort	58685	649350	1106.50%
cols2chars	ulong	13561	362318	2671.76%
cols2chars	ushort	50556	632911	1251.90%

In fact, some cases it turns out to be 24 times faster.

I haven't looked into too much detail on why, but I suspect a large amount of the reason is to do with the way the XS functions primarily walk along the internal UTF-8 representation of the strings, counting bytes, characters, and columns as they go, and returning the appropriate count(s) when the required. The pureperl implementation doesn't have direct access to the byte offsets, so only has character numbers to work to. The frequent character-to-byte or byte-to-character conversions at all the boundaries between the functions result in multiple UTF-8 byte skip counting steps along the string each time a function is entered or left, generally slowing it down.

As to the original test failure, it turned out to be entirely unrelated lack of locale support in the platform's libc. The XS implementations fail there in the same way. But having implemented the above improvements, I decided to leave them in anyway.

XS faster than Pure Perl; who'd have thought it?

Perl - IO::Async - version 0.41

Wow; seems I haven't been writing these posts as much as I should be. I last wrote about version 0.34, and just now I've uploaded version 0.41 to CPAN. Quite a bit changed between then and now, here's a rundown of the most important bits:

• Added IO::Async::FileStream. This behaves like a read-only IO::Async::Stream, but reads its data from a regular file on the filesystem. Like tail -f, or File::Tail, it watches the file for changes in size, and follows appended data.


• Added IO::Async::Function. This is a true IO::Async::Notifier subclass to represent an asynchronous block of code; which was previously handled by DetachedCode. Being a true Notifier subclass gives it many advantages, and should provide a better base to build other things on. IO::Async::Resolver is now a subclass of Function, not DetachedCode.


• Added IO::Async::Process. This is another IO::Async::Notifier subclass, this time to represent an external process.


• Support encoding parameter in IO::Async::Stream. This allows the Stream to handle text in some encoding, rather than simply raw bytes.


• Support first_interval parameter to IO::Async::Timer::Periodic. If supplied, this will be the first wait time when the timer is started. In particular, if it is zero the timer's first invocation will happen immediately.


• Allow Loop->listen to be extended via extensions, similar to ->connect. Such extensions as IO::Async::SSL are already set up to make use of this.


• Distribution now uses Test::Fatal rather than Test::Exception. The former is smaller and simpler, whereas the latter relies on clever tricks to hack on caller(), which sometimes breaks some setups.


• Added convenient method in IO::Async::Loop for handling socket addresses; extract_addrinfo. This recognises strings for common networking constants; 'inet', 'inet6' and 'unix' as socket families, 'stream', 'dgram' and 'raw' as socket types. These convenient forms are also recognised by the ->connect and ->listen methods.


• Now prefers to use the IPv6 support functions found in Perl 5.14's Socket module; only falling back to using Socket::GetAddrInfo in earlier perls.

Sleep Sorting with IO::Async and CPS

There's a bit of a silly meme going around lately; an implementation of a sorting algorithm that works by many parallel sleeps. So I thought I'd have a go at it from an IO::Async perspective.

use CPS qw( kpareach );
use IO::Async::Loop;

my $loop = IO::Async::Loop->new;

kpareach( \@ARGV,
   sub {
      my ( $val, $k ) = @_;
      $loop->enqueue_timer(
         delay => $val,
         code  => sub { print "$val\n"; goto $k },
      );
   },
   sub { $loop->loop_stop },
);

$loop->loop_forever;

This produces such output as:

$ perl sleepsort.pl 3 8 4 2 6 5 7 1
1
2
3
4
5
6
7
8

It's a little more verbose than I'd like it though. I have been pondering creating a CPS::Async module, which would provide some more simple CPS-like versions of the usual blocking primatives we're used to, like sleep and sysread. Using this new hypothetical module would lead to something looking like:

use CPS qw( kpareach );
use CPS::Async qw( ksleep );

kpareach( \@ARGV,
   sub {
      my ( $val, $k ) = @_;
      ksleep( $val, sub {
         print "$val\n";
         goto $k;
      } );
   },
   sub { CPS::Async::stop },
);

CPS::Async::run;

This would be a small wrapper around IO::Async, providing CPS-style functions that turn into method calls on some implied IO::Async::Loop object; similar to for example, the AnyEvent::Impl::IOAsync, which exposes an AnyEvent API using IO::Async.

I have plenty of other projects to keep me amused currently, but I'll sit it on the back burner in case something interesting happens that way...

libtermkey - read keypresses from terminals

I have just released version 0.8 of libtermkey. It contains a small set of bugfixes on the previous version (0.7), relating to handling the signal-raising keys (Ctrl-C, Ctrl-\, Ctrl-Z), gracefully handles EINTR from read(2) calls, and actually gets around to implementing the CSI u modified Unicode encoding scheme I documented a long time ago.

libtermkey is a library for reading keypress events (and in fact mouse events too) from a terminal, in a terminal-based application. I won't list all its points and features, but as a brief overview:

• It presents events to the application in a structure, containing basic key information and a bitfield of modifiers in effect, rather than a single flat enumeration integer, as curses tries to do. In this way, it can easily represent the various modifier-combinations on cursor keys, like arrows or PageUp/PageDown, and can easily represent any Unicode character vs. any special key.


• It supplies a pair of functions (termkey_strfkey and termkey_strpkey) for converting between these structural notations and plain-text human-readable strings, such as "Ctrl-PageUp". These assist with easy reporting of keypresses in applications, or for config file parsing.


• Perl bindings exist, primarily in the form of Term::TermKey.

Wearing Two Hats

A while ago, I wrote libtermkey, a C library for reading keypress events from a terminal. I wrote a Perl binding for it, Term::TermKey. On a separate note, I also maintain IO::Async, an event framework for Perl. Naturally, the combination of these two lead me to write an IO::Async module to handle libtermkey, Term::TermKey::Async. These all work together quite well.

However, these two things are separate considerations. There's nothing specific to Perl, in libtermkey, nor anything specific to IO::Async in Term::TermKey. After some thought, and discussions on #perl, I decided in the end, that I had to realise these were two separate concerns, two different problem domains, that neither should be allowed to influence the other. In short, I had to wear two hats.

With my libtermkey hat on, I went to join #poe and #anyevent on irc.perl.org, and talked my way around designing two new modules, which are now happily sitting on CPAN as well: POE::Wheel::TermKey and AnyEvent::TermKey.

With so many CPAN modules effectively being glue between two others (such as in the case of Term::TermKey::Async being the glue between Term::TermKey and IO::Async), it's often the case that at least one if not both sides of the module are written by the same author. It is important to recognise these cases, and to consider whether the community as a whole would be better served by taking a look around to see if other modules and other use cases need attention as well.

When wearing hats, it is important to remember which hat you are wearing, and only try to wear one hat at once.

Deterministic Random Testing

I've just written an implementation of a weighted random shuffle. Because the function is random, it won't return the same results every time. This makes it hard to unit-test; I can't just run it on some given input and assert it returns some given output. Indeed, by its nature, any ordering of the results is potentially valid. One way to solve this is to run it a large number of times, counting the frequency of various output results, and asserting that roughly the right proportion of results are returned. Of course, exactly how close "roughly right" is, is hard to determine.

This isn't a very satisfactory testing method, however. Get the tolerance too tight, and spurious random differences cause tests to fail unnecessarily. Too loose, and you might miss a subtle logic bug that skews the probabilities of some case.

The weighted random shuffle algorithm calls int rand $limit a number of times, each time passing in a small integer. This effectively uses the RNG like a dice roll, randomly selecting some integer 0 .. $limit - 1. Because each call takes a small integer, and because the algorithm is entirely deterministic for any given set of random results, this suggests a better testing method. If we could instead enumerate all possible returns of random numbers, each one exactly once, we can generate all possible results from the shuffle algorithm in their ideal proportions. Because this will be an exact deterministic count, free from randomness, we can assert exact values for the results.

So this is what I did. I've created a module, for now simply called Unrandom, which exports one function, unrandomly. It is used like the following:

use Unrandom 'unrandomly';

unrandomly {
  my $da = 1 + int rand 6;
  my $db = 1 + int rand 6;
  say "Roll 2d6: $da + $db = " . ($da+$db);
};

The unrandomly function has the effect of replacing the rand function with one under its control while it runs the block of code. It runs the block of code a number of times, enumerating the entire tree of possible return values, in a given deterministic order:

Roll 2d6: 1 + 1 = 2
Roll 2d6: 1 + 2 = 3
Roll 2d6: 1 + 3 = 4
Roll 2d6: 1 + 4 = 5
Roll 2d6: 1 + 5 = 6
Roll 2d6: 1 + 6 = 7
Roll 2d6: 2 + 1 = 3
Roll 2d6: 2 + 2 = 4
...
Roll 2d6: 6 + 5 = 11
Roll 2d6: 6 + 6 = 12

Because each possible combination is returned exactly once, we can unit test that this dice-rolling algorithm does in fact give us the right distribution of results; there will be exactly one 2, two 3s, etc... We don't have to run it a few million times, and check that we got "roughly" the right number; we can be exact.

While I'm using this code in a unit-test, there's nothing directly test-related in the code. It could be useful anywhere that statistical modelling is used, or other problems involving random integer generation.

I'm now just looking for a good name to call it, so I can extract it from the unit tests and give it a life of its own on CPAN.

Suggestions anyone?

Extended colour support, terminals, and ECMA-48

tl;dr summary: Terminal authors - please accept CSI 38:5:123 m as well as anything else, to set extended colours. NOTE THE COLON. Many terminals these days are starting to support extended colour modes; specifically things like 256 colours. They're all doing it wrong.

CSI 38;5;123 m

No no no no no. That is NOT what you think. It does not select colour 123 from palette 5. CSI arguments are separated by semicolons. This sets three unrelated SGRs; 38, 5, and 123. 38 sets a foreground colour to .. er.. nothing in particular. 5 is blinking mode, 123 has no defined meaning to my knowledge. All the other following are exactly identical:

CSI 5;38;123 m
CSI 38 m CSI 5 m CSI 123 m

ECMA-48 already defines a perfectly good way for parameters to take sub-parameters. It's the colon. The correct way to encode this concept is

CSI 38:5:123 m

Why does this matter? It matters for parsers not to have to understand what is going on. Consider

CSI 3;38:9:5:4:3:2:1;11;1

This is equivalent to

CSI 3 CSI 38:9:5:4:3:2:1 CSI 11; CSI 1

I.e. I have no idea what palette 9 is, but I can definitely parse out the contents of this SGR from the others, knowing exactly where it ends. I don't have to "just know" that palette 9 happens to take 5 parameters. The CSI encodes this. My own terminal emulator library, libvterm, already understands these colon-based arguments. It parses them correctly. This is important for other palettes that don't take just one value. For example, the RGB, RGBA, CMY, and CMYK palettes. It's vital to be able to parse out these sub-arguments from the single SGR 38 or 48. Standards exist for a reason, people. Please use them.

---

Edit 2012/12/20: actually, I have recently learned that xterm now supports this in its correct form as well, since xterm patch 282.