10 ms·

Inside font-rs, a font renderer written in Rust

430 points by beefsack 10y ago

amelius 10y ago
I always wonder why a distinction is made between font rendering and rendering arbitrary SVG shapes. In other words, couldn't this renderer be much more useful when generalized?
- rtpg 10y ago
  I would imagine that arbitrary SVG rendering is harder to get right? 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.
  - valarauca1 10y ago
    SVG standard includes JavaScript. So SVG renderers are very non-trivial to implement.
    - posterboy 10y ago
      hilarious
      - kbenson 10y ago
        In a "laugh because the only other option is to break down and cry" sort of way, yes.
  - amelius 10y ago
    > and considering how much text your machine is showing, the performance tricks could be extra useful 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.
- speps 10y ago
  The linked article[1] about stb_truetype seems to have polygons instead of fonts so it could be used for polygons or any vector. [1] http://nothings.org/gamedev/rasterize/ http://nothings.org/gamedev/rasterize/
- vardump 10y ago
  TrueType includes a virtual machine [1] for hinting. Text rendering also needs to alter shapes of glyphs for other reasons, like font weight and pseudo-italic. [1]: https://en.wikipedia.org/wiki/TrueType#Hinting_language https://en.wikipedia.org/wiki/TrueType#Hinting_language
- wmil 10y ago
  There are specific clarity optimizations that are important for font rendering but don't generalize to all SVG rendering.
  - wldcordeiro 10y ago
    You could generalize that to image rendering too, same reason why Photoshop and other tools have 'optimize for text' and 'optimize for art' as options.
- raphlinus 10y ago
  I think there is value in applying these ideas to SVG rendering as well. There are of course a bunch of things that are different. For SVG, buffers get large enough you'd probably want to do _some_ banded rendering because the accumulation buffer might otherwise get too big. 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.
  - kragen 10y ago
    I was thinking about using your prefix-sum approach for exactly that almost all of last night. I don't have an attack on the problem that I'm satisfied with yet: 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.
- stuaxo 10y ago
  Text is usually made up of lots of small solid shapes whereas SVG will usually have larger shapes, sometimes using effects such as gradients - so it's likely that different optimisations will work best on each one.
- glippiglop 10y ago
  I work on a project that uses Free type for text and an improved version of AntiGrain for SVG rendering. The thought of using AGG for the font rendering has already crossed my mind, but mainly for reducing the size of the codebase. Speed isn't really a concern to me because the glyphs are already being cached to internal bitmaps, after which the bottleneck is the drawing algorithm (which is straightforward anyway). Overall, it's not worth my time to change the font engine. 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.
- kevin_thibedeau 10y ago
  Font rendering makes some optimizations that aren't general purpose. Rendered glyphs are (may be) cached. Assumption of a single color. No self intersecting outlines. These allow font renderers to take shortcuts for performance.
- TheRealPomax 10y ago
  Fonts are not "collections of pictures", though, and haven't been since the mid 1980. Details in http://pomax.github.io/1449777175633/opentype-let-s-learn-how-modern-fonts-actually-work http://pomax.github.io/1449777175633/opentype-let-s-learn-ho... but the gist is that a font is a full, complex, 700-page-specced typesetting program that has to be run on a render engine, similar to how a game ROM is run on an emulator or hardware setup. Sure, you need the engine, but there is nothing to generalize: that engine needs to implement a really large spec, most of which is not "drawing a vector image".
nathancahill 10y ago
Neat. I can't help but wonder if this will fall victim to the "last 10% is the hardest" rule? Will going from tech demo to production ready remove the performance gain? 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.
- zellyn 10y ago
  Raph really, really knows his stuff. His interview on the New Rustacean podcast starts with a summary of his background: Gimp, Ghostview, android font rendering.
  - catawbasam 10y ago
    Yup, I still remember being blown away by his dissertation. That he is using Rust in earnest is enough reason for me to take another look at the language.
  - microcolonel 10y ago
    For what it's worth; Gimp, Ghostscript, and Android all use FreeType for text rendering. At best, they would require him to know how to use FreeType bitmaps correctly (i.e. gamma-correct blending, when to multiply colours in). Though he could easily go beyond that, it is very interesting stuff and I find it incredibly hard to stop myself from reading into FreeType.
  - cdbattags 10y ago
    Any chance we can get a link? Edit: Whoops, see below. And for the lazy: http://www.newrustacean.com/show_notes/interview/_2/index.html http://www.newrustacean.com/show_notes/interview/_2/index.ht... (credit to @wscott)
  - zellyn 10y ago
    Your 10x speed, 90% functionality caution is definitely warranted. I've lost count of how many times I've seen "we run Python/Ruby/Perl/whatever" 3x faster, just haven't implemented exceptions and monkey-patching yet. :-)
wscott 10y ago
Very interesting post. 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.html 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.
- untothebreach 10y ago
  Indeed, C <-> Rust interop is one of rusts design goals. The Rust Book goes over this a bit: https://doc.rust-lang.org/book/ffi.html#calling-rust-code-from-c https://doc.rust-lang.org/book/ffi.html#calling-rust-code-fr...
- steveklabnik 10y ago
  > I believe it should be possible to have rust compile to a library > that could be called from a normal C program. Not only that, but languages where you can use C as a way to extend them. Rust has been in production for years as "a Ruby gem written in Rust", for example.
publicfig 10y ago
There's also rusttype [1] that was written as an alternative to FreeType in Rust, I know it's being used at this point in Redox [2], which is an interesting project of a Unix-like operating system being written entirely in Rust to the best of my knowledge. I'm curious to see how the two compare at this time. [1] https://github.com/dylanede/rusttype https://github.com/dylanede/rusttype [2] https://www.redox-os.org/ https://www.redox-os.org/
- raphlinus 10y ago
  I did some measurements of rusttype and found it to be even slower than FreeType. That said, this is all open source and so I have confidence that the improvements will flow all the way, either through rusttype using the font-rs rasterizer, or font-rs becoming robust enough for downstream like Redox and Piston to adopt.
  - moosingin3space 10y ago
    Integrating parts of this into RustType would be awesome!
kibwen 10y ago
The author is in the thread on /r/rust if anyone has any questions: https://www.reddit.com/r/rust/comments/4vqpxx/inside_the_fastest_font_renderer_in_the_world/ https://www.reddit.com/r/rust/comments/4vqpxx/inside_the_fas... (Please ignore today's deliberately garish background image, we just turned MIR on and we're celebrating. :P )
- ufo 10y ago
  That warning about the web design shows that you know the HN crowd very well. Complaints about fonts, annoying Javascript and other things that make the site hard to read always get voted to the top :)
  - deleted 10y ago
    [deleted]
joosters 10y ago
Are fonts always rendered 'completely' these days? I thought that the fonts would be rendered once to a cache of bitmaps/textures, and then those bitmaps can be copied to the screen/buffer pretty much instantaneously. 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...
- microcolonel 10y ago
  There is a point. Subpixel positioning is important and it's hard to know how much memory will be taken up by the full set of characters. Because you can not know the advances(and hence the exact positions) before you render the characters, you can not render them ahead of time without quantizing the position and storing multiple bitmaps. This quickly becomes a non-optimization.
  - Ono-Sendai 10y ago
    Sure you could. Just resample the bitmap.
  - p0nce 10y ago
    What I do is rounding the glyph position to 1/4 of pixels, in my tests it has not much visual impact. That still mean in the worst case the glyph cache could contains 16x the same glyph, and that's before hinting enters the equation.
  - panic 10y ago
    You can get good subpixel rendering from a single bitmap using a larger prefiltered glyph: https://github.com/nothings/stb/tree/master/tests/oversample https://github.com/nothings/stb/tree/master/tests/oversample
- zellyn 10y ago
  On the parallel Reddit discussion, someone mentioned that the gain is less when rendering CJK scripts, since there are so many different glyphs.
- 10y ago
wmil 10y ago
This is actually an important use for Rust. Many font renders were initially written for speed on single user systems running trusted programs. 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.
- moosingin3space 10y ago
  My belief is that Rust today, in production, is best used in networking code, such as protocol parsers, but the interest in font rendering in Rust will help to push the priority of stabilizing SIMD up, which should help quite a bit with the applications where Rust lags in performance.
  - pcwalton 10y ago
    I haven't observed that the lack of stable SIMD makes Rust only suitable for networking code. You can easily use SIMD by writing in assembly (inline assembly, even), with unstable intrinsics, or even with autovectorization. In Servo, for example, we have large speedups over existing C++ codebases that have nothing to do with networking.
    - moosingin3space 10y ago
      Oh I'm a huge Rust fan and am using it in nearly everything, but I'd really like to use it in data analytics/linear algebra applications (it would be nice to be able to use a single language for this instead of the mash of Python, R, Octave, and C), and lack of stable SIMD has been an issue there.
    - vardump 10y ago
      It would be useful to be able to have an option for 16 (SSE)/32 (AVX)/64 (AVX512) byte aligned stack in Rust, to help with SIMD alignment requirements. That would help with SIMD related stack alignment code and reduce cases where dropping down to assembler is needed. Of course external ABI might need need to have normal alignment. 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.
sievebrain 10y ago
Surely the biggest win here is not so much the faster rendering, which is nice, but rather that font rendering is so often a source of remote code execution exploits ...
- pcwalton 10y ago
  I think Rust is at its strongest when it achieves both improved performance and better security. Not everyone cares about performance, and not everyone cares about security, but most people care about one or the other.
- danbruc 10y ago
  Looking at the source code it does not look like this implementation includes the virtual machine for hinting which seems the most likely source of remote code execution vulnerabilities in a text rendering system.
c-smile 10y ago
Those manual use/optimization of SIMD are done in C anyway. 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"?
- vardump 10y ago
  > Those manual use/optimization of SIMD are done in C anyway. 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.c 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)); } } Also consider top level: https://github.com/google/font-rs/tree/master/src https://github.com/google/font-rs/tree/master/src > 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)."
  - dman 10y ago
    Any reasons why the sse code wouldnt be written in rust itself?
    - phpnode 10y ago
      No SIMD intrinsics yet
Mathnerd314 10y ago
For a while now, I've been wondering if font rendering could be improved by using a Lanczos filter instead of a box filter for anti-aliasing. (Conceptually, when you compute the pixel coverage you are convoluting the image with a box filter and then sampling at each pixel's center) The performance impact might be too high, but I haven't seen anyone try the experiment.
- vardump 10y ago
  > if font rendering could be improved by using a Lanczos filter instead of a box filter 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. [1]: https://en.wikipedia.org/wiki/Font_hinting https://en.wikipedia.org/wiki/Font_hinting [2]: https://en.wikipedia.org/wiki/Subpixel_rendering https://en.wikipedia.org/wiki/Subpixel_rendering
  - Ericson2314 10y ago
    I think on today's high density mobile phone screens, these techniques are no longer needed.
    - wtallis 10y ago
      They can still provide some benefit, but it's true that modern high-DPI mobile screens don't need the heavy-handed hinting of Windows and doing subpixel rendering when the subpixel orientation keeps changing as the device is rotated can be more trouble than it's worth.
    - TheRealPomax 10y ago
      if those were the only screens in the world, I would agree wholeheartedly, but there are millions, if not more, non-mobile screens in use today. This problem is unlike to go away with high-dpi technology in the next 20 maybe even 50 years.
nathell 10y ago
Extremely impressive and exciting, kudos to the author! 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.
Drdrdrq 10y ago
I'm curious: is font rendering speed something that regular user would notice in his day to day use? Maybe in battery life? Or is this important just for some specialized (designers'?) use? 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).
- moosingin3space 10y ago
  A reduction in font rendering time would make it easier to meet higher framerates, especially on mobile when rendering CJK characters, as mentioned on the Reddit thread.
- rspeer 10y ago
  Right now you can basically DoS gnome-terminal on Ubuntu by sending it a screenful of Thai text (or any of many similar scripts where most adjacent letters have ligatures to each other, but Thai is by far the most common). It slows down to rendering like 40 characters per second. 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.
  - anthk 10y ago
    gnome-terminal is slow. Try st, or rxvt.
    - rspeer 10y ago
      You must mean something else besides rxvt, which doesn't support Unicode.
      - welterde 10y ago
        Probably meant rxvt-unicode and not plain rxvt, which doesn't appear to be under development anymore.
Const-me 10y ago
Impressive! > 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.

430 points by beefsack 10y ago

I always wonder why a distinction is made between font rendering and rendering arbitrary SVG shapes. In other words, couldn't this renderer be much more useful when generalized?

rtpg 10y ago
I would imagine that arbitrary SVG rendering is harder to get right? 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.
- valarauca1 10y ago
  SVG standard includes JavaScript. So SVG renderers are very non-trivial to implement.
  - posterboy 10y ago
    hilarious
    - kbenson 10y ago
      In a "laugh because the only other option is to break down and cry" sort of way, yes.
- amelius 10y ago
  > and considering how much text your machine is showing, the performance tricks could be extra useful 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.
speps 10y ago
The linked article[1] about stb_truetype seems to have polygons instead of fonts so it could be used for polygons or any vector. [1] http://nothings.org/gamedev/rasterize/ http://nothings.org/gamedev/rasterize/
vardump 10y ago
TrueType includes a virtual machine [1] for hinting. Text rendering also needs to alter shapes of glyphs for other reasons, like font weight and pseudo-italic. [1]: https://en.wikipedia.org/wiki/TrueType#Hinting_language https://en.wikipedia.org/wiki/TrueType#Hinting_language
wmil 10y ago
There are specific clarity optimizations that are important for font rendering but don't generalize to all SVG rendering.
- wldcordeiro 10y ago
  You could generalize that to image rendering too, same reason why Photoshop and other tools have 'optimize for text' and 'optimize for art' as options.
raphlinus 10y ago
I think there is value in applying these ideas to SVG rendering as well. There are of course a bunch of things that are different. For SVG, buffers get large enough you'd probably want to do _some_ banded rendering because the accumulation buffer might otherwise get too big. 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.
- kragen 10y ago
  I was thinking about using your prefix-sum approach for exactly that almost all of last night. I don't have an attack on the problem that I'm satisfied with yet: 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.
stuaxo 10y ago
Text is usually made up of lots of small solid shapes whereas SVG will usually have larger shapes, sometimes using effects such as gradients - so it's likely that different optimisations will work best on each one.
glippiglop 10y ago
I work on a project that uses Free type for text and an improved version of AntiGrain for SVG rendering. The thought of using AGG for the font rendering has already crossed my mind, but mainly for reducing the size of the codebase. Speed isn't really a concern to me because the glyphs are already being cached to internal bitmaps, after which the bottleneck is the drawing algorithm (which is straightforward anyway). Overall, it's not worth my time to change the font engine. 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.
kevin_thibedeau 10y ago
Font rendering makes some optimizations that aren't general purpose. Rendered glyphs are (may be) cached. Assumption of a single color. No self intersecting outlines. These allow font renderers to take shortcuts for performance.
TheRealPomax 10y ago
Fonts are not "collections of pictures", though, and haven't been since the mid 1980. Details in http://pomax.github.io/1449777175633/opentype-let-s-learn-how-modern-fonts-actually-work http://pomax.github.io/1449777175633/opentype-let-s-learn-ho... but the gist is that a font is a full, complex, 700-page-specced typesetting program that has to be run on a render engine, similar to how a game ROM is run on an emulator or hardware setup. Sure, you need the engine, but there is nothing to generalize: that engine needs to implement a really large spec, most of which is not "drawing a vector image".

nathancahill 10y ago

Neat. I can't help but wonder if this will fall victim to the "last 10% is the hardest" rule? Will going from tech demo to production ready remove the performance gain? 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.

zellyn 10y ago
Raph really, really knows his stuff. His interview on the New Rustacean podcast starts with a summary of his background: Gimp, Ghostview, android font rendering.
- catawbasam 10y ago
  Yup, I still remember being blown away by his dissertation. That he is using Rust in earnest is enough reason for me to take another look at the language.
- microcolonel 10y ago
  For what it's worth; Gimp, Ghostscript, and Android all use FreeType for text rendering. At best, they would require him to know how to use FreeType bitmaps correctly (i.e. gamma-correct blending, when to multiply colours in). Though he could easily go beyond that, it is very interesting stuff and I find it incredibly hard to stop myself from reading into FreeType.
- cdbattags 10y ago
  Any chance we can get a link? Edit: Whoops, see below. And for the lazy: http://www.newrustacean.com/show_notes/interview/_2/index.html http://www.newrustacean.com/show_notes/interview/_2/index.ht... (credit to @wscott)
- zellyn 10y ago
  Your 10x speed, 90% functionality caution is definitely warranted. I've lost count of how many times I've seen "we run Python/Ruby/Perl/whatever" 3x faster, just haven't implemented exceptions and monkey-patching yet. :-)

wscott 10y ago

Very interesting post. 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.html 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.

untothebreach 10y ago
Indeed, C <-> Rust interop is one of rusts design goals. The Rust Book goes over this a bit: https://doc.rust-lang.org/book/ffi.html#calling-rust-code-from-c https://doc.rust-lang.org/book/ffi.html#calling-rust-code-fr...
steveklabnik 10y ago
> I believe it should be possible to have rust compile to a library > that could be called from a normal C program. Not only that, but languages where you can use C as a way to extend them. Rust has been in production for years as "a Ruby gem written in Rust", for example.

publicfig 10y ago

There's also rusttype [1] that was written as an alternative to FreeType in Rust, I know it's being used at this point in Redox [2], which is an interesting project of a Unix-like operating system being written entirely in Rust to the best of my knowledge. I'm curious to see how the two compare at this time. [1] https://github.com/dylanede/rusttype https://github.com/dylanede/rusttype [2] https://www.redox-os.org/ https://www.redox-os.org/

raphlinus 10y ago
I did some measurements of rusttype and found it to be even slower than FreeType. That said, this is all open source and so I have confidence that the improvements will flow all the way, either through rusttype using the font-rs rasterizer, or font-rs becoming robust enough for downstream like Redox and Piston to adopt.
- moosingin3space 10y ago
  Integrating parts of this into RustType would be awesome!

kibwen 10y ago

The author is in the thread on /r/rust if anyone has any questions: https://www.reddit.com/r/rust/comments/4vqpxx/inside_the_fastest_font_renderer_in_the_world/ https://www.reddit.com/r/rust/comments/4vqpxx/inside_the_fas... (Please ignore today's deliberately garish background image, we just turned MIR on and we're celebrating. :P )

ufo 10y ago
That warning about the web design shows that you know the HN crowd very well. Complaints about fonts, annoying Javascript and other things that make the site hard to read always get voted to the top :)
- deleted 10y ago
  [deleted]

joosters 10y ago

Are fonts always rendered 'completely' these days? I thought that the fonts would be rendered once to a cache of bitmaps/textures, and then those bitmaps can be copied to the screen/buffer pretty much instantaneously. 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...

microcolonel 10y ago
There is a point. Subpixel positioning is important and it's hard to know how much memory will be taken up by the full set of characters. Because you can not know the advances(and hence the exact positions) before you render the characters, you can not render them ahead of time without quantizing the position and storing multiple bitmaps. This quickly becomes a non-optimization.
- Ono-Sendai 10y ago
  Sure you could. Just resample the bitmap.
- p0nce 10y ago
  What I do is rounding the glyph position to 1/4 of pixels, in my tests it has not much visual impact. That still mean in the worst case the glyph cache could contains 16x the same glyph, and that's before hinting enters the equation.
- panic 10y ago
  You can get good subpixel rendering from a single bitmap using a larger prefiltered glyph: https://github.com/nothings/stb/tree/master/tests/oversample https://github.com/nothings/stb/tree/master/tests/oversample
zellyn 10y ago
On the parallel Reddit discussion, someone mentioned that the gain is less when rendering CJK scripts, since there are so many different glyphs.
10y ago

wmil 10y ago

This is actually an important use for Rust. Many font renders were initially written for speed on single user systems running trusted programs. 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.

moosingin3space 10y ago
My belief is that Rust today, in production, is best used in networking code, such as protocol parsers, but the interest in font rendering in Rust will help to push the priority of stabilizing SIMD up, which should help quite a bit with the applications where Rust lags in performance.
- pcwalton 10y ago
  I haven't observed that the lack of stable SIMD makes Rust only suitable for networking code. You can easily use SIMD by writing in assembly (inline assembly, even), with unstable intrinsics, or even with autovectorization. In Servo, for example, we have large speedups over existing C++ codebases that have nothing to do with networking.
  - moosingin3space 10y ago
    Oh I'm a huge Rust fan and am using it in nearly everything, but I'd really like to use it in data analytics/linear algebra applications (it would be nice to be able to use a single language for this instead of the mash of Python, R, Octave, and C), and lack of stable SIMD has been an issue there.
  - vardump 10y ago
    It would be useful to be able to have an option for 16 (SSE)/32 (AVX)/64 (AVX512) byte aligned stack in Rust, to help with SIMD alignment requirements. That would help with SIMD related stack alignment code and reduce cases where dropping down to assembler is needed. Of course external ABI might need need to have normal alignment. 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.

sievebrain 10y ago

Surely the biggest win here is not so much the faster rendering, which is nice, but rather that font rendering is so often a source of remote code execution exploits ...

pcwalton 10y ago
I think Rust is at its strongest when it achieves both improved performance and better security. Not everyone cares about performance, and not everyone cares about security, but most people care about one or the other.
danbruc 10y ago
Looking at the source code it does not look like this implementation includes the virtual machine for hinting which seems the most likely source of remote code execution vulnerabilities in a text rendering system.

c-smile 10y ago

Those manual use/optimization of SIMD are done in C anyway. 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"?

vardump 10y ago
> Those manual use/optimization of SIMD are done in C anyway. 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.c 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)); } } Also consider top level: https://github.com/google/font-rs/tree/master/src https://github.com/google/font-rs/tree/master/src > 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)."
- dman 10y ago
  Any reasons why the sse code wouldnt be written in rust itself?
  - phpnode 10y ago
    No SIMD intrinsics yet

Mathnerd314 10y ago

For a while now, I've been wondering if font rendering could be improved by using a Lanczos filter instead of a box filter for anti-aliasing. (Conceptually, when you compute the pixel coverage you are convoluting the image with a box filter and then sampling at each pixel's center) The performance impact might be too high, but I haven't seen anyone try the experiment.

vardump 10y ago
> if font rendering could be improved by using a Lanczos filter instead of a box filter 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. [1]: https://en.wikipedia.org/wiki/Font_hinting https://en.wikipedia.org/wiki/Font_hinting [2]: https://en.wikipedia.org/wiki/Subpixel_rendering https://en.wikipedia.org/wiki/Subpixel_rendering
- Ericson2314 10y ago
  I think on today's high density mobile phone screens, these techniques are no longer needed.
  - wtallis 10y ago
    They can still provide some benefit, but it's true that modern high-DPI mobile screens don't need the heavy-handed hinting of Windows and doing subpixel rendering when the subpixel orientation keeps changing as the device is rotated can be more trouble than it's worth.
  - TheRealPomax 10y ago
    if those were the only screens in the world, I would agree wholeheartedly, but there are millions, if not more, non-mobile screens in use today. This problem is unlike to go away with high-dpi technology in the next 20 maybe even 50 years.

nathell 10y ago

Extremely impressive and exciting, kudos to the author! 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.

Drdrdrq 10y ago

I'm curious: is font rendering speed something that regular user would notice in his day to day use? Maybe in battery life? Or is this important just for some specialized (designers'?) use? 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).

moosingin3space 10y ago
A reduction in font rendering time would make it easier to meet higher framerates, especially on mobile when rendering CJK characters, as mentioned on the Reddit thread.
rspeer 10y ago
Right now you can basically DoS gnome-terminal on Ubuntu by sending it a screenful of Thai text (or any of many similar scripts where most adjacent letters have ligatures to each other, but Thai is by far the most common). It slows down to rendering like 40 characters per second. 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.
- anthk 10y ago
  gnome-terminal is slow. Try st, or rxvt.
  - rspeer 10y ago
    You must mean something else besides rxvt, which doesn't support Unicode.
    - welterde 10y ago
      Probably meant rxvt-unicode and not plain rxvt, which doesn't appear to be under development anymore.

Const-me 10y ago

Impressive! > 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.