Inside font-rs, a font renderer written in Rust
medium.com
medium.com
It sounds like you're claiming that FreeType is slower because the parsing/accumulation implementations are slower. It's far from my area of expertise, but wouldn't 20 y/o open source software as prevalent as FreeType have optimized those code paths?
Edit: Author is a heavyweight in font rendering circles. Excuse my ignorance. Just wary of "10x faster with 90% of functionality!" benchmarks.
Edit: Whoops, see below. And for the lazy: http://www.newrustacean.com/show_notes/interview/_2/index.ht... (credit to @wscott)
(And the whole podcast is an easy recommandation. Googlers talking about Android dev stuff from an insider perspective)
This is one of those performance drains across many languages that we often don't see because our weak languages don't let us. Manifesting an array for a consumer that only wants to iterate on it once, in order, with no backtracking, is a common antipattern. Just as I'd look askance at any putative "next big language" that doesn't have any sort of closure support, I look askance at "next big languages" that don't have iterators.
You'd be surprised how often SIMD goes unused. libpng, for example, doesn't use it on x86…
Outside of games, scientific computing, and a few other fields, it's notable how little of the hardware in our devices actually gets put to use.
In terms of automation, SIMD is hard to automatically implement (i.e. through the compiler) with a lot of traditional programming languages (e.g. C), and hard to add to dynamic languages, as you end up adding extra code paths/jit passes for each new type of simd/parallelism hardware construct available.
Do you mean doesn't use it explicitly? If so, GCC is still happy to find quite a few spots to automatically inject it. On my arch system:
$ objdump -d /usr/lib/libpng.so | grep -c xmm
316
$ objdump -d /usr/lib/libgif.so | grep -c xmm
0No, 20 y/o software had Heartbleed. Just because software is old doesn't mean it's battle-tested.
> The current state of the code is quite rough. The code isn't well organized, and it's basically not ready for prime time.
From what I can see in https://github.com/google/font-rs/blob/master/src/font.rs, this is what is missing:
* support of CFF-based fonts (that is "postscript-flavored outlines" (i.e. cubic) OTF files)
* "Advanced Typographic Tables" (see Opentype spec: https://www.microsoft.com/typography/otspec/otff.htm), this is what is needed to render more complex non-latin languages like Arabic etc, because it defines context-specific replacements and positioning, but also opentype-level kerning
* support for the kerning table
* support for slightly more exotic TTF variations like EOT and WOFF for webfonts
* hinting support for smaller rendering sizes
Most of these things are supported by Freetype, and are probably a considerable amount of work to add. Once you add them into the rendering calculations, the abstractions in the code would have to be refactored and the code would become more complex and probably slower.
Having said that, it's still a nice implementation and easy to read, something I wouldn't necessarily say about Freetype ;)
These features don't have much to do with the core rasterization algorithm, which is where the vast majority of the time is typically spent. So I wouldn't expect things to go slower.
In any case, hinting just changes point positions. It doesn't affect the way the rasterizer works at a fundamental level, I don't believe.
[1] https://developer.apple.com/fonts/TrueType-Reference-Manual/...
FreeType also doesn't handle Advanced Typographic Tables. For that you need HarfBuzz. Note that rendering and shaping are usually considered to be separate processes - one doesn't expect a font rendering library to handle shaping
Other than hinting nothing you've mentioned should affect the rasterization performance.
The tradeoffs that made the most sense 20 years ago are not those that would lead to the fastest implementation on current hardware. This is not so much the Freetype is unoptimized, it's that old, possibly wrong optimizations are pretty much baked in now...
Modern CPU have massively more cache and have vectorization instructions, which make the optimal solution very different from the one optimal for the Pentium II that was top of the line when Freetype was first conceived... It's also acceptable to use vastly more memory, Freetype dates from a time where a beefy desktop machine had maybe 32Mb of RAM...
(Please ignore today's deliberately garish background image, we just turned MIR on and we're celebrating. :P )
Vector rendering creates a lot of edge cases that C tends to ignore.
The initial X-Box soft mod hack was done by loading a font with negative values in key fields. Microsoft had brought over the Windows font rendering code, and that wasn't written with hostile fonts in mind.
In Servo, for example, we have large speedups over existing C++ codebases that have nothing to do with networking.
Ability to selectively align functions too would be nice. Sometimes it's nice to get them to 64-byte boundary, to reduce icache latency and waste. You usually only have 512 64-byte lines of L1 instruction cache, sometimes it pays to be able to choose where it's spent.
Also autovectorization doesn't support many uses and can be quite brittle AFAIK.
I think Rust is absolutely amazing, but stabilized SIMD support is right up at the top of my wishlist.
Note that the New Rustacean podcast did an interview with the author of this post, Raph Levien. That was very interesting and he did touch on this program. http://www.newrustacean.com/show_notes/interview/_2/index.ht...
I believe it should be possible to have rust compile to a library that could be called from a normal C program.
> I believe it should be possible to have rust compile to a library
> that could be called from a normal C program.
After all, there's no point re-doing all the calculations to draw all the curves in a letter 'g' when the output is going to look just the same as the last time you drew it...
This quickly becomes a non-optimization.
Beyond the sub-pixel aliasing and CJK questions other people asked, a fair number of people use languages like Arabic, Devangari, etc. which have complex rules for how adjacent characters affect rendering (you can see something like this in English with a font like Zapfino which has ligatures: http://download.linotype.com/free/howtouse/ZapfinoTips_e.pdf). I would imagine all of that would conspire against cache hit rates more than we might guess.
That's not to say this isn't great work but just that any time something involves text rendering it seems to inevitably sprout special cases on the special cases.
Font renderers that cache keep a cache of bitmaps for glyphs that it has previously rendered. Since you need a separate bitmap for each Unicode codepoint or ligature × font size × subpixel offset, the cache could potentially get huge.
So, they cap the number of bitmaps that get cached and evict some. But when you're animating a font's size or dealing with non-Latin languages, you're churning through so many unique bitmaps that you end up not getting much value from the cache.
They are. But (a) non-Latin languages often miss in the cache; (b) subpixel positioning makes cache misses happen more often; (c) sometimes people animate font size, negating the optimization; (d) we care about initial load time.
I do hope this project gains traction, though the advantage I see is in replacing another piece of legacy code with safe(r) one (Rust).
I work with multilingual corpora and I live in fear of accidentally scrolling into the Thai parts. I would report this bug but I don't know whose bug it is.
So maybe I'm not a regular user, but font rendering speed is something I notice.
It seems what we have here is a tradeoff: the font rendering in your terminal can be good, or it can be fast, but perhaps not both given the current options. urxvt and st are doing some kind of very low-level font rendering that doesn't match the fonts I see most of the time on Ubuntu. Whatever antialiasing algorithm they use, if you let them antialias, is a smudgy mess, and not something I would want to look at all day.
The result only makes me appreciate more the idea that good, fast, text rendering is something that a new library could help us achieve.
https://wiki.archlinux.org/index.php/Font_configuration#Hint...
I have the hinting style set to slight.
You don't want an ideal filter for rendering fonts -- you want sharp edges instead. A lot of work [1][2] has been done to achieve this.
In font rendering, alignment to pixel boundaries is intentional, it's called hinting. So you could say aliasing is used for an advantage.
I assume 4K will come do predominate, but we'll see.
It depends on your philosophy: https://blog.codinghorror.com/font-rendering-respecting-the-... http://www.joelonsoftware.com/items/2007/06/12.html
In general antialiasing and font hinting are at odds; you want one but not the other. With recent displays, the pixels are small enough that you can use anti-aliasing all the time, and no hinting: http://lh5.ggpht.com/-tsgwX-9fsRc/U6armqjI6QI/AAAAAAAAB9E/Bw...
Subpixel rendering is just another anti-aliasing technique; it can be used on any bitmap.
Of course, it's also true that the sinc filter is not the best possible. There's interesting research on shearlet transformations http://colorlab.no/content/download/46570/721686/file/2014_C... and other weird filters http://www.ansatt.hig.no/mariusp/publications/Pedersen2015_I.... Or just avoid the filtering stuff entirely and optimize a whole-eye model: http://michaelfrankdeering.com/blog/projects/eye_work/eye_mo...
> dense representations have a huge advantage when data-parallelism is an option
Sparse or dense isn’t binary choice, it’s possible to combine the two to have best of both.
When I was working on similar problem in 3D space and with much larger dataset, I represented my voxels as sparse collection of small dense blocks. The blocks are small enough to fit in a single cache line, small enough to save a lot of RAM space + bandwidth because many are empty, but inside they are dense and large enough to benefit from SIMD parallelism.
However, for 2D images that only take a few hundred kb RAM dense buffer is probably better because fits in L1 or at least L2 cache.
With fonts you can probably cache a lot of the rendering (even considering things like ligatures), and considering how much text your machine is showing, the performance tricks could be extra useful.
So SVG renderers are very non-trivial to implement.
Well, an SVG-based drawing program has to re-render a lot of the same SVG every time the user makes a little change. Also, when animating an SVG scene, a lot of the shapes are redrawn continuously.
[1]: https://en.wikipedia.org/wiki/TrueType#Hinting_language
Another serious potential win in SVG is that you might be able to interleave the area integration with alpha compositing / masking. Could end up pretty darned fast.
1. Render each path to a fresh pixel buffer, alpha-compositing it down onto the final canvas. Advantage: straightforward, works for sure. Disadvantage: you need a lot of multiplies per pixel.
2. Partition paths into "layers" of nonoverlapping paths, render each layer as a unit, and composite each new layer down onto the final canvas. Overlapping opaque paths can be incorporated into the same layer as whatever is below them by cutting an overlap-shaped hole in what's below before adding in the new path; although that involves some intersection tests to know where to stop, my intuition is that it will be a big win. Advantages: straightforward, probably faster than the previous one. Disadvantages: the partitioning is a potentially costly extra step (one of those things that makes me wonder if it's NP-complete to do it optimally), and there are still potentially many multiplies per pixel.
3. Separately accumulate a numerator (total premultiplied color) and denominator (total alpha) for each pixel, then divide in the end. Advantages: You avoid doing lots of work per pixel. Disadvantages: This is a weighted sum, not alpha blending. Alpha blending is a different thing. So the result is wrong. Also, an honest division per pixel is more expensive than quite a number of multiplications, although maybe you could cheat on the final division with a table of approximate multiplicative inverses or something. So this would probably be super slow.
4. Find a different group other than ℤ/256ℤ in which to do prefix-sum that somehow gives you the right results. Then you can just render all the edges into the same buffer and do a single vectorizable prefix-sum operation over it.
Advantages: This sounds super fast.
Disadvantages: It seems clear that this group is going to have to be able to represent the entire Z-ordered stack of colors at every pixel, because if I'm looking at some translucent green on top of translucent red on top of opaque black on top of pale blue, and I reach the right (negative) edge of the opaque black path, somehow I have to have remembered the blue thing underneath in order for it to peek through, which suggests to me that I need an unbounded number of bits per pixel to implement this scheme, which probably is not going to admit an actually fast implementation. In effect it has to reduce to the second approach, except that the software has to deal with the stack of layers once for every pixel. Or is there some magical way around this, at least for a fast-path case?
This part is probably obvious to you, Raph, but you can do SVG linear gradients with two prefix-sum passes instead of one, where the first pass just runs over signed gradient stops and gradient clipping boundaries, and then you draw the signed path boundaries into the buffer before the second prefix-sum pass. (Is that clear? I suspect it may be too abbreviated.)
I suspect that with three prefix-sum passes you could do a decent quadratic-spline† approximation of arbitrary gradients, including the weird skew cone gradients SVG calls "radial gradients". But I haven't worked out the details.
I know you don't have a lot of time to hack on this stuff right now, but would you have time to provide feedback if I were to hack on it a bit? I imagine that I'd run into any number of places where talking to you about it for half an hour could save me days of wasted effort.
† here I'm talking about what Carl de Boor calls "splines", which I know disagrees with your usage of "splines". I think you called them "B-splines" in your dissertation.
I think you're going for something much more complicated than what I had in mind. My idea is simply to have two modes other than accum buffer -> 8 bit alpha mask. One would be accum buffer + constant RGBA color -> update RGBA buffer. (By update I mean read an RGBA pixel, do the compositing, and write the composited pixel in place). The other would be accum buffer + source RGBA buffer -> update RGBA buffer. Of course, it's possible to imagine interleaving even more operations in the generation of the source RGBA buffer, but at some point the register pressure overcomes the r/w bandwidth.
Prefix-sum is not a particularly fast SIMD operation, due to the horizontal data dependency. I chose it for font-rs because I don't know of any faster ones that can get the job done. For just computing gradients, it's almost certainly going to be faster to compute it directly (it's simple multiply-add in the case of linear gradients) than to try to strength reduce. The same is no doubt true for SVG radial (cone) gradients.
When the gradient doesn't have any sharp creases or singularities, a very reasonable strategy is to compute it in lower resolution and then up-res, say 2x or 4x to keep the math super-simple. When it does have creases, it might make sense to decompose into regions and use different approaches in different regions.
In any case, it sounds like you may be re-inventing Cairo or Skia here. Might make sense to take a closer look at what they do and whether there's truly any low-hanging fruit left. I know that Skia has a bunch of SIMD optimizations already.
But this is fun stuff to think about and experiment with. I certainly don't want to discourage you.
The really nice thing about using an SVG engine to draw text is the potential for applying runtime effects, transformations and so forth. However that's an entirely different use case and can be done through SVG as it stands. Most of the time you want your text to be on the horizontal and easy to read, and vanilla FT is fine for that.
It would be interesting to compare the memory footprint and code size of font-rs vs freetype; comparing just speed doesn't give the full picture.
What exactly is so Rust'y in the code? If to compare with C/C++? What is the main benefit of using Rust? Or is it just a test like "you can do that in Rust too"?
C seems to be used only for SSE intrinsics support. ~16 LoC of "C".
This is all C in the whole project, if you really think you can call it as such:
https://github.com/google/font-rs/blob/master/src/accumulate...
void accumulate_sse(const float *in, uint8_t *out, uint32_t n) {
__m128 offset = _mm_setzero_ps();
__m128i mask = _mm_set1_epi32(0x0c080400);
__m128 sign_mask = _mm_set1_ps(-0.f);
for (int i = 0; i < n; i += 4) {
__m128 x = _mm_load_ps(&in[i]);
x = _mm_add_ps(x, _mm_castsi128_ps(_mm_slli_si128(_mm_castps_si128(x), 4)));
x = _mm_add_ps(x, _mm_shuffle_ps(_mm_setzero_ps(), x, 0x40));
x = _mm_add_ps(x, offset);
__m128 y = _mm_andnot_ps(sign_mask, x); // fabs(x)
y = _mm_min_ps(y, _mm_set1_ps(1.0f));
y = _mm_mul_ps(y, _mm_set1_ps(255.0f));
__m128i z = _mm_cvtps_epi32(y);
z = _mm_shuffle_epi8(z, mask);
_mm_store_ss((float *)&out[i], (__m128)z);
offset = _mm_shuffle_ps(x, x, _MM_SHUFFLE(3, 3, 3, 3));
}
}
> What is the main benefit of using Rust?
Safety and performance.
From the article:
"With the SIMD speedup, font-rs is approximately 7.6x faster than FreeType in larger sizes (keep in mind that 42 pixels/em is the default for xxhdpi Android devices)."
You might have missed that in his post.
One of the big gains mentioned in the article for Rust was using iterators instead of a one-time-use vector, which is very hard in C, would currently be best done with Boost in C++, but is a core idiom in Rust.
For optimized real-world code, the innermost, hottest, loop is almost always machine-specific, and a superset of C is used if the language of implementation doesn't have intrinsics for the particular machine feature one wants to access.
I have only dabbled in Rust, but it is common to see other high-level languages where given X amount of effort the high-level language implementation is faster than a C implementation that could be implemented with a similar amount of effort. It's almost certainly possible to create an iterator version with a custom stack allocator in C that matches the performance of the Rust version, but you will be creating an ad-hoc, informally specified, buggy version of two of rust's core features[1].
C++ is a different beast entirely as the language is on track to completely reinvent itself every 6 years, so it's likely in a few years that you could port the Rust version nearly unchanged to C++17 or C++20, and there's probably a Boost library that allows it now.
Maybe misundestood somethin. But hard or requiring boost? Isn't this basically what you meant?
class enumerating_parser { uint8_t* pos; uint8_t* end; enumerating_parser(const uint8_t* bytes, int len):pos(), end(pos + len){} bool next(ParserResult& out){ if(pos == end) return false; // do parsing here and move pointer forward } };
Rust has algebraic datatypes, memory safety, pattern matching, etc, - those are actual things that are, if not hard, then at least tiringly verbose to do in C and C++;
0: enumerating_parser now becomes struct enumerating_parser{}, the constructor becomes a factory function while next() takes in the parser as a state parameter.
Further, Rust's monomorphizing approach to generics means that you can count on efficient code. Iterators over a slice typically elide the bounds checking, reliably.
Of course you can use these patterns in other languages, but you lose something, specifically, clarity and safety. I believe that's the reason you see them used all the time in Rust and rarely in C and C++.
My answer was to the specific claim that an iterator using the "next" formulation would be hard to use in C++ - it's not, and it makes several pieces of code much nicer than using the default iteration scheme of raw index or pointer-hopping.
So, the intent was not to make a statement "we can do that in C++, Rust has no merit in this regard" but rather, "you should not shy away from this nice pattern if you are forced to use C++ in your daily work". This intent was not that obvious in the message's context, though.
i.e. enumerating_parser p(source, source_len); ParseResult r; while(p.next(r)){// forward context of r forwards}.
So use unsigned len or add more code to check your inputs or just use Rust where this sort of unsafe pointer arithmetic doesn't even compile.
"Oooh, it's made a lot of progress recently! Funny thing, I actually started experimenting with this stuff pre-Rust 1.0. Last I looked at the SIMD crate, it was missing a whole bunch of stuff, and my style is to use fairly exotic SIMD instructions when they can help (for example, _mm_shuffle_epi8 is available in tmmintrin.h but not pmmintrin.h.
This is a technology demo, so using a not-yet stabilized feature seems in scope. Perhaps I'll try the SIMD crate for writing the ARM version."