A Faster Perl Runtime in Tiny Steps

Booking.com uses the Perl programming language heavily across its entire technical infrastructure. At the size of our infrastructure, even small performance improvements can translate into hefty savings, not to mention the exciting new features that we will implement with those spare CPU cycles. For this reason, we are very happy to announce that we are now funding Dave Mitchell, prominently known for his many years of high-quality contributions to the Perl language implementation, to improve the Perl runtime’s performance one small step at a time.

Written by Steffen Müller

The initial work started in February. Dave is working at the pace of his choosing and sharing some details on his progress on a monthly basis. The summary for February has already hit the development mailing list. Dave’s summaries are necessarily concise as they’re intended for experts. I’ll expand on some of the changes here.

Dereferencing Overloaded Objects

This means that we can have the more faithful overload support of recent Perls and have it be efficient, too.

Faster Array Access (Sometimes)

$foo[3]

is faster than this:

$foo[$bar]

This likely comes as a surprise to few. Alas, the optimization strikes a run-time/space trade-off in that it only has 8 bits to store constant indexes in. If you think outside the box just a little bit, you’ll realize that this is not a huge limitation. Code that does $array[5913] is rare. Code like $array[0], that is small constant indexes, is the overwhelmingly most common case of constant-index accesses.

Dave’s change is as simple as it is effective. Previously, indexes in the range between 0 and 255 were optimized. Dave changed this to be between -128 and 127. This is a net win because again, $array[-1] is common to get the last element, whereas $array[200] is very rarely seen with a literal constant.

Avoid Doing Meaningless Work in the Runtime

Dave’s work in this area means there are no more OPs of type OP_NULL that are ever executed. That is, any optimization now always manages to apply the more thorough elimination of needless OPs. This change still resides on a branch for testing.

Less Overhead on Common Hash Operations

Dave’s keys() optimization is much deeper than meets the eye. Understanding what it does requires a little insight into how Perl's hash data structures are organized internally and a bit of their history.

Historically a hash was a fairly complex structure, which included preallocated storage for iterator state. This meant they were large. At some point it was realized that many hashes are never iterated. This meant that we could lazily allocate the iterator structure. The way we chose to do this was to embed it at the end of the bucket array, forcing us to realloc() the bucket array on "first iteration". This has the advantage that hashes which are not traversed are smaller in memory. The trade off is that the realloc() can be slow.

Dave’s patch takes advantage of the observation that there is no need for per-hash iterator state when running keys() and similar operations. We traverse the whole hash in one go, so the iterator need not be stored against the hash, and instead a preallocated structure can be used by keys() for its purposes.

Until you consider hash order randomization, things are really that simple. But it so happens that keys() and each() must produce the same output order. The per-hash randomization data is stored in the iterator structure, so there is no way for the optimized keys() to guarantee the same order as a subsequent each() would (vice versa is not a problem as each() must create the iterator struct). The solution is to figure out how to store the randomization data in the base structure.

Unfortunately, this isn’t so easy. All members of the existing structure appear fully used, so we need to figure out how to squeeze more bits of data in without expanding space usage needlessly. Multiple options are still on the table. The structure currently looks like this:

struct xpvhv {
HV* xmg_stash; /* class package */
union _xmgu xmg_u;
STRLEN xhv_keys; /* total keys, including placeholders */
STRLEN xhv_max; /* subscript of last element of xhv_array */
};

At the most abstract what we want to do is add another STRLEN (U32) member called xhv_rand to the structure, but we want to do it without making the structure larger.

Now it turns out that xhv_max contains the size of the bucket array, and that is always a power of two. That in turn means it uses 32 bits to store 5 bits worth of information (for performance). So at the cost of some arithmetic we can squeeze out 27 valuable bits of space. xhv_keys contains the total number of keys, which in the current implementation will always be smaller than xhv_max, so hypothetically we could somehow store both in the same field. There is also the observation that the random data need only be as long (in terms of bits) as xhv_max is. This means that if we could ensure that any hash with more than K buckets must have a preallocated iterator structure, then for smaller hashes we can store the max (or keys) and random data in the same struct member.

An entirely different solution would be to use a hash of the address of the data structure as the initializer to xhv_rand(), this however has the potential to reduce security.

What was worked on was the logic to guarantee that hashes of a certain size have a preallocated iterator structure, plus, the logic to pack the keys and randomization data into the xhv_keys structure when the number of buckets is smaller than 2**16. This also included an implementation of hashing the data structure address as the initializer.

The changes discussed here will not land in the main development branch (blead in perl parlance) before the Perl 5.20 release.

More Compact Code for Leaving Scopes

Micro-Optimizations for Perl Function Calls

Summary

Would you like to be a Developer at Booking.com? Work with us!

Booking.com Development

Software development at Booking.com

Booking.com Development

Software development at Booking.com

booking.development

Written by

Booking.com Development

Software development at Booking.com