mattst88's blog

Optimizing pixman for Loongson: Process and Results

mattst88@gmail.com (Matt Turner) — Thu, 17 May 2012 00:00:00 -0400

The Lemote Yeeloong is a small notebook that is often the computer of choice for Free Software advocates, including Richard Stallman. It's powered by an 800 MHz STMicroelectronics Loongson 2F processor and has an antiquated Silicon Motion 712 graphics chip. The SM712's acceleration features are pretty subpar for today's standards, and performance of the old XFree86 Acceleration Architecture (XAA) that supports the SM712 has slowly decayed as developers move to support newer hardware and newer acceleration architectures. In short, graphics performance of the SM712 isn't very good with new X servers, so how can we improve it?

If you don't care about how pixman was optimized and just want to see the results, you can skip ahead.

pixman, the pixel-manipulation library used by cairo and X has MMX-accelerated compositing functions, written using MMX via C-level intrinsic functions, which allow the programmer to write C but still have fine-grained control over performance sensitive MMX code.

Last summer I began optimizing graphics performance of the OLPC XO-1.75 laptop. The Marvell processor it uses supports iwMMXt2, a 64-bit SIMD instruction set designed by Intel for their XScale ARM CPUs. The instruction set is predictably very similar to Intel's original MMX instruction set. By design, Intel's MMX intrinsics also support generating iwMMXt instructions, so that the same optimized C code will be easily portable to processors supporting iwMMXt. With a relatively small amount of work (as compared to writing compositing functions in ARM/iwMMXt assembly) I had pixman's MMX optimized code working on the XO-1.75 for some nice performance gains.

The Loongson 2F processor also includes a 64-bit SIMD instruction set, very similar to Intel's MMX. Its SIMD instructions use the 32 floating-point registers, and like iwMMXt it provides some useful instructions not found in x86 processors until AMD's Enhanced 3DNow! or Intel's SSE instruction sets.

So just like I did with the XO-1.75, I planned to use pixman's existing MMX code to optimize performance on my Yeeloong.

While Intel's MMX intrinsic functions are well designed, well tested, well supported, and widely used, the Loongson intrinsics are none of these. In fact, they're incomplete, badly designed, and used no where I can find (indeed, all of the instances of Loongson-optimized SIMD code I have found are written in inline assembly, which is no surprise given the state of the intrinsics). Of course, the gcc manual doesn't tell me this, so I learned it only after trying to use them with pixman.

Aside: let me pretend that I'm designing and implementing Loongson's vector intrinsics, covering an instruction set very similar to MMX, which already has an excellent set of intrinsic functions. Why would I create my own incompatible set, instead of implementing the same interface that lots of software already use?!

Using the Loongson vector intrinsics, pixman passed the test suite, and objdump verified that gcc was successfully generating vector instructions, but the performance was terrible. gcc apparently was not privy to the knowledge that the integer data types returned by the intrinsics were actually stored in floating point registers, so in between any two vector instructions you might find three or four instructions that simply copied the same data back and forth between integer and floating-point registers.

punpcklwd	$f9,$f9,$f5
    dmtc1	v0,$f8
punpcklwd	$f19,$f19,$f5
    dmfc1	t9,$f9
    dmtc1	v0,$f9
    dmtc1	t9,$f20
    dmfc1	s0,$f19
punpcklbh	$f20,$f20,$f2

This path lead no where, so I decided to take the hint from previous programmers and forget that the Loongson intrinsics exist. I still wanted to use pixman's MMX code, so I implemented Intel's MMX intrinsics myself using Loongson inline assembly. Object code size was significantly smaller and performance was better, in fact much better in some select functions, but overall was still a net loss. There must have been optimization opportunities that I was missing.

On the XO-1.75 the MMX code is faster than the generic code, so I didn't recognize inefficiencies in the MMX code the first time I worked with it, but with the Loongson it was necessary that I find and fix them. The great thing is that optimizations to this code benefit x86/MMX, ARM/iwMMXt, and Loongson.

I took a look at the book Dirty Pixels at the suggestion of pixman's maintainer, Søren Sandmann. In it, I discovered that the original MMX instruction set lacked an unsigned packed-multiply high instruction which would be useful for the over compositing operation. To work around the lack of this instruction, an extra two shifts and an add had to be used. AMD recognized this inefficiency and added the instruction in Enhanced 3DNow! and later Intel did the same with SSE. I modified the pix_multiply function to use the new instruction, and the resulting object code size shrunk by 5%.

I realized that the expand_alpha, expand_alpha_rev, and invert_colors functions that mix and duplicate pixel components could be reduced from a combined total of around 30 instruction to a single instruction each. This change further reduced object code size by another 9%.

After that, I focused on eliminating unnecessary copies to and from the vector registers. Consider this code:

__m64 vsrc = load8888 (*src);

The code loads *src into an integer register, and then load8888 loads and expands the value into a vector register. Instead, it's simpler and faster to load from memory into a vector register directly. By counting the number of dmfc1 (doubleword move from floating-point) and dmtc1 (doubleword move to floating-point) instructions I could determine which functions.

After reducing the number of unnecessary copies and adding a number of other optimizations (list available here) I was ready to see if the Yeeloong was more usable.

Results gathered from cairo's perf-trace tool confirm the real-world performance improvements given by the pixman optimizations. The image columns show the time in seconds to complete a cairo-perf-trace workload when using 32 bits per pixel and likewise image16 for 16 bits per pixel. The first column in both image and image16 groupings is the time to complete the workload without using Loongson MMI code. The second column is time to complete the workload after pixman commit c78e986085, the commit that turns on the Loongson MMI code. The third column is the time to complete the workload with pixman-0.25.6 which has many more optimizations.

	image				image16
evolution	32.985	29.667	28.752	14.7% faster	27.314	23.870	22.960	19.0% faster
firefox-planet-gnome	197.982	180.437	169.532	16.8% faster	220.986	205.057	199.077	11.0% faster
gnome-terminal-vim	60.799	50.528	50.792	19.7% faster	51.655	44.131	43.561	18.6% faster
gvim	38.646	32.552	33.570	15.1% faster	38.126	34.453	35.457	7.5% faster
ocitysmap	23.065	18.057	17.516	31.7% faster	23.046	18.055	17.543	31.4% faster
poppler	43.676	36.077	35.498	23.0% faster	43.065	36.090	35.534	21.2% faster
swfdec-giant-steps	20.166	20.365	20.469	no change	22.354	16.578	14.473	54.4% faster
swfdec-youtube	31.502	28.118	24.168	30.3% faster	44.052	41.771	38.577	14.2% faster
xfce4-terminal-a1	69.517	51.288	50.838	36.7% faster	62.225	53.309	44.297	40.5% faster

May 29th edit: the % faster numbers were previously calculated as a percent difference between the initial workload times and the final workload times. I realized that this calculation's result is not strictly a metric of how much faster the code is. To calculate that, the new formula is (1/initial - 1/final) / (1/initial)) which calculates the percent difference in terms of operations/second. This number is % faster. The table has been updated accordingly.

As the results show, real-world performance is improved by the Loongson MMI code. I can tell a difference when using GNOME 3 (in fallback mode) on my Yeeloong.

So far this has been very successful. I've optimized pixman on an interesting platform, learned a new instruction set, and in the process found many opportunities to optimize the MMX code on x86 and ARM. I still see a bunch of things to work on with just these compositing operations alone. Beyond that, there are many other things to do like bilinear and nearest scaling functions (which are extremely important for Firefox performance). And beyond that, I've improved my understanding of pixman's code and have a few ideas for improvements in general.

Thanks to

Danny Clark, who runs freedomincluded.com, for providing me with a Lemote Yeeloong laptop for my work on Gentoo's MIPS port.
Søren Sandmann and Siarhei Siamashka for reviewing and helping me improve my code.

New multilib N32 Gentoo MIPS Stages

mattst88@gmail.com (Matt Turner) — Tue, 02 Aug 2011 00:00:00 -0400

Gentoo/MIPS has been in, well, not great shape for quite some time. When I was going through Gentoo recruitment, there were no stages (used for installing Gentoo) newer than 2008, so this was one of the main things I wanted to improve, specifically by creating new N32 ABI stages. Even though the N32 (meaning New 32-bit) ABI was introduced in IRIX in 1996 to replace SGI's o32 (Old 32-bit) ABI, Linux support for N32 has lagged behind until the last few years. Now, I'm pleased to unofficially announce new multilib N32 stages and that we'll be supporting as the preferred ABI.

MIPS has three main ABIs: o32 (32-bit integer and pointer), N32 (64-bit integer, 32-bit pointer), N64 (64-bit integer and pointer). Compared with N32 and N64, o32 is very restrictive. Very few function arguments are passed in registers; only half the number of floating point registers are usable; no native 64-bit integer datatype; no long double type. (see SGI's MIPSpro N32 ABI Handbook for details). Offering N32 as the default ABI means better performance, sometimes 30% more, just by removing the unnecessary restrictions a 32-bit ABI imposes on 64-bit CPUs. Providing multilib stages (ie, stages with glibc and gcc built for all three ABIs) gives the user flexibility to switch to another ABI relatively easily if desired, while also allowing him to reduce build times by switching to an N32-only profile.

The process of creating N32 (and especially multilib) stages wasn't straight forward. Our profiles were long unmaintained and in many cases totally broken. There were lots of keywording bugs open for mips, many where the MIPS was the last team to complete the request by years. There were actually some real bugs discovered too, like 354877 and 358149, usually caused by the incorrect assumption that the lib directory is always a symlink to lib32. All in all, I've reduced the number of open bugs for MIPS down to ~20.

Work needed to be done to catalyst, Gentoo's release building tool. Since the end of June, I've made 15 commits cleaning, fixing, and adding to the mips support code in catalyst. Other developers like Sebastian Pipping have also resumed work on a project that had otherwise been minimally maintained since the beginning of the year.

The last major component in reviving Gentoo's MIPS support is to create installation media, preferably in an automated manner. I've acquired two Broadcom BCM91250A MIPS development boards (and should be receiving a third soon), but they need disks, controllers, RAM, and cases. For that, I wrote a funding Proposal to build three MIPS development computers (pdf) and had it approved by the Gentoo Foundation. Things seem to be going well in acquisitions (track progress) so I hope to have the project completed in the next few months with the systems automatically building stages for a wide variety of MIPS systems.

Initially, I used a big-endian 2006.1 N32 stage and had to bootstrap my system with a series of at least 20 hacks (not a fun experience) until it was usable enough that I was able to build a clean N32 stage. From there, using crossdev I built a multilib toolchain, and with a few more hacks I was able to build a multilib stage.

With that in the past, I've been building stages that can be used to seed the automated stage creation system to come. At this point, my TODO list looks like this:

Big Endian
- multilib
  - (done) mips3 -mfix-r4000 -mfix-r4400 (for SGI Indy and Indigo2)
  - (done) mips4 (for SGI Indy and O2)
  - (done) r10k (for SGI Indigo2, Octane)
  - (done) mips64 (for Broadcom Sibyte systems)
- o32
  - mips32 (for embedded mips systems)
  - mips1 (for everything else)
Little Endian
- multilib
  - mips3 -Wa,-mfix-loongson2f-nop (for Loongson 2 systems)
  - mips4 (for Cobalt systems)
  - mips64 (for Loongson 3, Broadcom Sibyte systems)
- o32
  - mips32 (for embedded mips systems)
  - mips1 (for everything else)

The final touches will be to create bootable media like CD, USB, and netboot images.

All stages are available in the experimental/mips/stages/ directory (as soon as the files propagate) of a Gentoo Mirror.

Hopefully by the time I'm able to convince Lemote (or, who?) to send me a Loongson 3A laptop, installing and using Gentoo/MIPS will be a fun and pleasant experience.

The State of Alpha Linux

mattst88@gmail.com (Matt Turner) — Sun, 14 Dec 2008 00:00:00 -0500

Software is never finished; it's forgotten. There is always one more enhancement to be made or one little quirk to work out. Sometimes there are even big problems. It happens from time to time. It's expected, and it's expected that the problems will be fixed. After spending quite a bit of time recently working with Linux on the Alpha platform, I've come to realize we face some very serious problems. And unfortunately, these may not ever be fixed, putting in jeopardy the future (hah!) of Alpha/Linux. I decided to articulate these problems in an email to the Linux on Alpha Processors mailing list in order to inform and ultimately find solutions and breathe a bit of life back into Alpha/Linux. I'd like to think that Alpha/Linux isn't a piece of forgotten software, not yet.

The State of Alpha Linux

We're all subscribed to this list because we use a dying platform. We do what we can to keep it going, but in recent months the State of Alpha Linux has been deteriorating at an accelerated rate.

Let me outline some issues facing us today:

We have no glibc/Alpha maintainer [1]
Kernel development for Alpha is comatose
We can't run modern X.Org [2]

To make things worse, for such a small group of users, we're much too segregated and disorganized. For instance, how many (of the only four) Gentoo/Alpha maintainers are subscribed to this list? Debian/Alpha? How many realized we were without a glibc maintainer? That we can't use X.Org 7.4?

If this trend continues, we will completely first lose X.Org support. I even had an X.Org developer tell me he didn't care [about Alpha support] when I pinged him about an Alpha bug he had originally filed [3]!

We'll later lose glibc support. As it stands now, Alpha isn't even in the main tree [4]. I'm not sure what version Debian ships, but Gentoo is 3 versions behind at 2.6.1. Newer than that and the test suite causes a hard lock [5]. How much longer is it going to be before 2.6 is incompatible with the latest version and we begin to lose the ability to use other modern software?

While we may never lose kernel support, it will certainly begin to lag behind other platforms more and more. Bugs begin to take longer and longer to be fixed [6]. Release candidate kernels as late in the cycle as rc-8 of the 2.6.28 series fail to compile on Alpha [7]. This is definitely a worrying sign.

It is certainly expected that as a platform ages, it slowly loses its users and developers. In 1999, many average users knew or we're interested in learning Alpha assembly language, were interested in support for Alpha among Free Software, and were interested in programming for the platform. Obviously this cannot be the case today. We don't expect that it should.

We, the ones who do wish to see our platform live on, even if only a little longer, should focus on fixing what we can and maintaining what we already have.

Whether Fedora adds Alpha as a Second Tier Architecture is trivial in comparison to these issues. We should focus on making sure we have working software for Fedora/Alpha before we consider how to properly market it.

We, the small band of Alpha users, need to work together. We have the same problems, why should we work separately on them?

In order to facilitate better communication among Alpha users, developers, please use the Alpha IRC channel on Freenode, #alpha, and the Wiki [8]. If you have unused hardware that may be useful to developers, consider donating it.

From here, it's up to us to find solutions to these problems.

Ideas and Suggestions requested.

Matt Turner

What can we do? I think there are a couple things we need to do, namely:

Consolidate our efforts by consolidating distributions. With as few users as we have, we have fewer developers. There's no use in testing packages on Debian or Fedora when they're already tested in Gentoo.
Demand that Alpha remain supported. Projects, including projects integral to the Linux desktop such as X.Org, need to know that we do still use Alpha hardware and that we want to be supported. Make yourself heard in #xorg-devel and appropriate mailing lists.
Experienced developers need to take the lead. We understand that it's hard to justify time spent working on Alpha-related issues. We do not ask much. We just ask that you not abandon us.

If we can do these things, we will be on the road to recovery.

Does Anyone Care About Fixing Bugs?

mattst88@gmail.com (Matt Turner) — Sat, 13 Dec 2008 00:00:00 -0500

As time goes on, alternative architectures like Alpha and PA-RISC slowly lose their userbase. Experienced developers move on to things that interest them more. Emphasis isn't put on fixing bugs for these aging platforms, and the level of support slowly erodes. Eventually a small hardcore userbase is all that is left. The Gentoo Bugzilla showed this effect on the Alpha platform. All nontrivial bugs were left to rot. What's worse, many bugs were so old that the software containing them wasn't even in Portage anymore, yet no one closed the bug report or asked if it was fixed. One, a two-and-a-half-year-old bug about a failing cipher algorithm in libmcrypt caught my eye. I decided I'd give fixing it a shot.

The project's KNOWN-BUGS file stated

- cast-256 and rc6 do not work properly on Alpha (64 bit) machines

Fittingly, the bug was filed by a developer who has since retired. An automated test suite included with libmcrypt reported a failing cipher, CAST-256. Maybe it's a bug with gcc. Months pass. If it is, it's a bug across both 3.x and 4.x series. Years pass. Maybe we'll just mask the failure.

No one seemed to want to fire up vi and check the code.

I decided I'd compile the same version side by side on my AMD64 desktop and my UP1500 Alpha. Both compile cleanly, and I can reproduce the failing case quickly. The first thing I check is the test suite itself by adding print statements and comparing the output between the AMD64 and Alpha systems. All the start-up code looks fine. The problem has to be in the library itself, which is what I expect.

Finally, I find that the results begin to vary during a function call to _mcrypt_set_key. Continuing, I slowly isolate the failing code to the k_rnd macro, then the f1 macro, and finally to the rotl32 macro.

The rotl32 macro rotates bits left in a 32-bit memory cell. The macro and its siblings look like

#define rotl32(x,n)   (((x) << ((word32)(n))) | ((x) >> (32 - (word32)(n))))
#define rotr32(x,n)   (((x) >> ((word32)(n))) | ((x) << (32 - (word32)(n))))
#define rotl16(x,n)   (((x) << ((word16)(n))) | ((x) >> (16 - (word16)(n))))
#define rotr16(x,n)   (((x) >> ((word16)(n))) | ((x) << (16 - (word16)(n))))

I confirmed that this function did yield different results on AMD64 and Alpha by writing a small test program. Guessing, I figured that this implementation wasn't compatible with Alphas and that I could easily find another working implementation. In the Linux Kernel's include/linux/bitops.h file, they had virtually the same implementation. No luck there.

After a few hours of scouring the internet for quick-fix solutions, I turned to the Alpha Architecture Handbook and look up Alpha's shift instructions, sll and srl.

SxL   Ra.rq,Rb.rq,Rc.wq
Rc <- LEFT_SHIFT (Rav, Rbv<5:0>)      !SLL
Rc <- RIGHT_SHIFT(Rav, Rbv<5:0>)      !SRL

Beyond the terse syntax, this means that only six bits of the shift argument matter. The designers did this because with the Alpha's 64-bit wide registers, it doesn't make sense to implement instructions (and circuitry) to shift more than 63 times. Just the same, the rotl32 macro is only supposed to operate on 32-bit numbers, so it doesn't make sense to rotate more than 31 times.

The result of rotating 32 times should be the same as the number input, since it would rotate the bits the entire width of the field. On Alpha though there are more than 32-bits in each register, so shifting 32 times doesn't leave the bits in place. It moves them into the upper part of the register.

By masking the shift argument and ignoring all but the first five bits, I fixed the problem.

#define rotl32(x,n)   (((x) << ((word32)(n & 31))) | ((x) >> (32 - (word32)(n & 31))))
#define rotr32(x,n)   (((x) >> ((word32)(n & 31))) | ((x) << (32 - (word32)(n & 31))))
#define rotl16(x,n)   (((x) << ((word16)(n & 15))) | ((x) >> (16 - (word16)(n & 15))))
#define rotr16(x,n)   (((x) >> ((word16)(n & 15))) | ((x) << (16 - (word16)(n & 15))))

This bug didn't affect AMD64, since it has 32-bit shift instructions as well as 64-bit. Undoubtedly though, had this been a problem on AMD64 instead of an obscure and aging architecture such as Alpha, it would have been fixed in a heartbeat.

It's amazing that such a simple fix was needed to squash a bug that (1) was reported by a Gentoo/Alpha developer, and (2) had been in the tracker for two-and-a-half years.

Now, I need to check on that Kernel code. Who knows how long it's contained this bug!

Open Sourcing Compaq's Alpha Tools for Linux

mattst88@gmail.com (Matt Turner) — Wed, 16 Jul 2008 00:00:00 -0400

I'm in the (long and arduous) process of becoming a Gentoo/Alpha developer. This involves, firstly, becoming an Architecture Tester. This in turn, requires that I complete a quiz, mail it to the head of the Alpha team and wait. The developer who manages the alpha arch testers, of which there are none, currently, has been missing in action for 18 days.

Once I prove myself worthy, or whatnot, I'll then complete a longer version of the arch tester quiz. Once my quiz has been reviewed, I'll be mentored for 30 days. After this 30 day period, I'll officially be a Gentoo/Alpha developer.

At this point, I'll try to get Compaq's alpha compilers and libraries back into portage in one fashion or another. libots is already in portage. The math library, libcpml, whose value I showed will be next on my agenda. Compaq's C, C++, and FORTRAN compilers, having been unmaintained for years now, have quite a few incompatibilities with modern Linux distributions. I think the best course of action for these is to get them into a portage overlay.

Compaq's alpha optimized compilers, unmaintained and bit rotting, still hold a wealth of knowledge. Compaq's cc still produces code much better than gcc in certain cases. libcpml and libots have incredibly optimized routines for all sorts of common functions. It's such a shame for them to rot as they're doing now.

With this attitude, I emailed Linda Knippers of HP, who in some capacity orcestrated the AdvFS code release under the GPL.

Hi Linda,

There are a few tools and libraries Compaq/HP has provided for Alpha Linux in the past that have been totally unmaintained in the last few years but still hold great value and knowledge to the open source community. I'm emailing to (1) see if there's any possibility that they may be open sourced in the future, or (2) be directed to contact someone more appropriate.

The tools and libraries in question are Compaq's Alpha-Optimized C, C++, and FORTRAN compilers, libots, libcpml, libcxml, and ladebug. Other Tru64 tools that we Alpha Linux users would love to use include spike and pixie.

Do you know of any plans to release any code for any (hopefully all) of these products? It seems a shame to have them bit rot when GNU Compiler Developers could learn a thing or two from ccc, and when the GNU libc Developers could incorporate libcpml routines into their math library and so forth.

Thank you for your time,

Matt Turner

She kindly responded (9 minutes later!) and told me that although she didn't know of any plans to open source these products, that it may be something HP would consider. She forwareded my mail to a former Tru64 developer to get his thoughts.

While I don't have code in hand (yet), it appears that they are at minimum receptive to this idea. Hopefully in the near future we'll be reading through Digital/Compaq's code, learning more about alpha optimization, and implementing what we learn in gcc and glibc.

I'll definitely post back any new information I find out.