6 ms·

I respectfully disagree that CPUs are better than GPUs at font rendering :) There are a few related things that can be said. Doing fast, high quality font rend

I respectfully disagree that CPUs are better than GPUs at font rendering :) There are a few related things that can be said. Doing fast, high quality font rendering on a GPU is hard; it's much easier on a CPU. Further, the traditional rasterization pipeline of a GPU is not good at rendering fonts. Fortunately, modern GPUs also have compute shaders, which are programmed somewhat like regular computers but just with an astonishingly high number of threads. This is the topic of my research, and I intend to publish quantitative measurements backing up these assertions before long. Early results look promising.

danielvaughn 5y ago
You probably know about Slug, but just in case: https://sluglibrary.com https://sluglibrary.com I don't know much about the font space, but enough to know it's a really hard problem, and the slug team seems to do a really good job.
- raphlinus 5y ago
  Absolutely, and I don't want to claim I'm the first or only one doing font rendering on GPU. There's Slug as you pointed out, Pathfinder and Spinel as Jasper cited, and also interesting experimental work including GLyphy by Behdad and algorithms by Evan Wallace and Will Dobbie, plus a whole series of academic papers including "Massively Parallel Vector Graphics," "Random Access Vector Graphics," and others. However, I would say that a common thread is that doing this well is hard. There's no straightforward cookbook scheme that people can just implement, and there are always tradeoffs. Slug is used in a number of games (and congrats to Eric for winning those licenses), but not as far as I know in any UI toolkits, and there are reasons for that.
  - moonchild 5y ago
    > Slug is used in a number of games (and congrats to Eric for winning those licenses), but not as far as I know in any UI toolkits, and there are reasons for that Presumably because its antialiasing is crap? But there's nothing inherent to fragment-oriented approaches that prevents you from doing good aa, and they slot nicely into the existing rasterization pipeline (which is why slug has fewer feature level requirements than pathfinder). They also permit arbitrary domain transformations (some caveats here as you have to calculate a bounding box still), and given appropriate space partitioning should not be significantly slower than scanline algorithms. Also: UI toolkits are not known for being on the leading edge of graphics research. I think fastuidraw demonstrates this rather well. Insofar as there is exciting work happening in industry, it is mainly happening in web browsers; and I would expect mozilla and google to devote their efforts pathfinder and skia, respectively.
    - Arelius 5y ago
      > Presumably because its antialiasing is crap? No, Slug’s technique can handle AA and do it well. The problem with Slug for general purpose UI frameworks is it needs to do a lot of pre-processing on it’s data to do the good job it does.
      - moonchild 5y ago
        Slug aa is only 1-dimensional. From the paper (end of section 2): > Adding and subtracting these fractions from the winding number has the effect of antialiasing in the direction of the rays. Averaging the final coverages calculated for multiple ray directions antialiases with greater isotropy, but at a performance cost. Considering only rays parallel to the coordinates axes is a good compromise, especially when combined with supersampling, as discussed later. I.E. you don't get a real 2-d coverage result, only an amalgamation of a number of 1-d coverage results; and you must trade off performance and quality. Other approaches do not require such a tradeoff. Analytic 2-d coverage can be done more cheaply than n 1-d samples (n is probably in the neighborhood of 4-6), and produces better (mathematically ideal, albeit with uncomfortable caveats) results. (Note 4-6 samples don't mean 4-6x slower, due to space partitioning, buffers, and other fixed costs, as well locality. And I think slug takes 2 samples by default as is.)
  - danielvaughn 5y ago
    Oh I wasn’t pointing it out as a critical response to it being your thesis. I’m actually very interested to see how it turns out, because I’m digging into this space at the moment. I’m trying to build a platform-agnostic styling language specifically for UI/UX designers, and it’s leading me down the path of “render everything via WebGPU”. Is there a way I can follow your progress? Very keen on hearing more about your research if/when it’s ready.
marcan_42 5y ago
> which are programmed somewhat like regular computers but just with an astonishingly high number of threads. But they aren't that; they are actually wide vector processors, which means groups of threads need to be doing the same thing for it to perform properly! Branches and divergent control flow kill GPU performance. I'm sure you already know this, but I'm just pointing out for other folks reading. If GPUs were just CPUs with stupidly high core counts then things would be way easier, but it's more complicated than that.
- derefr 5y ago
  But any Turing-complete operation can be mapped mechanistically into a branchless ISA, can’t it? One of those “one-instruction” ISAs, for example, where every instruction is also a jump. Vector processors would compute on those just fine, just like they compute matrix-multiplication problem isomorphisms just fine. Or, for a more obvious/less arcane restatement: can't the shader cores just be given a shader that's an interpreter, and a texture that's a spritesheet of bytecode programs?
  - Jasper_ 5y ago
    Yes, we can make GPU programs that render vector images this way, but they tend to be slower than an equivalent CPU program. Branches are not the problem, GPUs handle those just fine now actually. The problem is duplicated work. GPUs have cores that are individually much, much slower than a CPU, but make up for this by having lots and lots of them running in parallel. Having those cores all run the same serial interpreter does not give you increased parallelism, so the result is slower. Designing algorithms for the GPU requires rethinking your dataflow and structure to exploit the parallel nature of the GPU. GPUs are not just a "go fast" button.
    - derefr 5y ago
      Well, sure; but the problem of font rendering specifically is an "embarrassingly parallel" one, isn't it? If you've got 1000 glyphs at a specific visual size to pre-cache into alpha-mask textures; and you've got 1000 GPU shader cores to compute those glyphs on; then each shader core only needs to compute one glyph once. Can a CPU really be so much faster than these cores that it can run this Turing-complete font rendering program (which, to be clear, is already an abstract machine run through an interpreter either way, whether implemented on the CPU or the GPU) consisting of O(N) interpreted instructions, O(N) times, for a total of O(N^2) serial CPU computation steps; in less than the time it takes the O(N) GPU cores to run only O(N) serial computation steps each? Especially on a modern low-power system (e.g. a cheap phone), where you might only have 2-4 slow CPU cores, but still have a bounty of (equally slow) GPU cores sitting there doing mostly nothing? If so, CPUs are pretty amazing. But even if it were true that it'd be faster in some sense (time to first pixel, where the first rendered glyph becomes available?) to render on the CPU — accelerators don't just exist to make things faster, they also exist to offload problems so the CPU can focus on things that are its comparative advantage. Analogies: - An apprentice tradesperson doesn't have to be better at a delegated task than their mentor is; they only need to be good enough at the task to free up some time for the mentor to focus on getting something higher-priority done, that the mentor can do and the apprentice (currently) cannot. For example, the apprentices working for master oil painters did the backgrounds, so the master could focus on portrait details + anatomy. The master could have done the backgrounds faster! But then that time would be time not spent working on the foreground. - Ethernet cards. CPUs are fast enough to "bit bang" even 10GBe down a wire just fine; but except under very specific situations (i.e. dedicated network-switches where the CPU wants to process every packet synchronously as it comes in), it's better that they don't, leaving the (slower!) Ethernet MCU to parse Ethernet frames, discard L2-misdirected ones, and DMA the rest into kernel ring-buffer memory. - Audio processors in old game consoles like the SNES's S-SMP and the C64's SID — yes, the CPU could do everything these could do, and faster; but if the CPU had to keep music samples playing in realtime, it wouldn't have much time to do things like gameplay (which usually goes together with playing music samples!) Offloading font (or generalized implicit-shape) rendering to the GPU might not make sense if you're just computing letterforms for billboard textures in a static 3D scene (rather the opposite!) but in a game that wants to do things like physics and AI on the CPU, load times can likely be shorter with the GPU tasked with the font rendering, no? Especially since the rendered glyph-textures then don't have to be loaded into VRAM, because they're already there.

danielvaughn 5y ago

You probably know about Slug, but just in case: https://sluglibrary.com https://sluglibrary.com I don't know much about the font space, but enough to know it's a really hard problem, and the slug team seems to do a really good job.

raphlinus 5y ago
Absolutely, and I don't want to claim I'm the first or only one doing font rendering on GPU. There's Slug as you pointed out, Pathfinder and Spinel as Jasper cited, and also interesting experimental work including GLyphy by Behdad and algorithms by Evan Wallace and Will Dobbie, plus a whole series of academic papers including "Massively Parallel Vector Graphics," "Random Access Vector Graphics," and others. However, I would say that a common thread is that doing this well is hard. There's no straightforward cookbook scheme that people can just implement, and there are always tradeoffs. Slug is used in a number of games (and congrats to Eric for winning those licenses), but not as far as I know in any UI toolkits, and there are reasons for that.
- moonchild 5y ago
  > Slug is used in a number of games (and congrats to Eric for winning those licenses), but not as far as I know in any UI toolkits, and there are reasons for that Presumably because its antialiasing is crap? But there's nothing inherent to fragment-oriented approaches that prevents you from doing good aa, and they slot nicely into the existing rasterization pipeline (which is why slug has fewer feature level requirements than pathfinder). They also permit arbitrary domain transformations (some caveats here as you have to calculate a bounding box still), and given appropriate space partitioning should not be significantly slower than scanline algorithms. Also: UI toolkits are not known for being on the leading edge of graphics research. I think fastuidraw demonstrates this rather well. Insofar as there is exciting work happening in industry, it is mainly happening in web browsers; and I would expect mozilla and google to devote their efforts pathfinder and skia, respectively.
  - Arelius 5y ago
    > Presumably because its antialiasing is crap? No, Slug’s technique can handle AA and do it well. The problem with Slug for general purpose UI frameworks is it needs to do a lot of pre-processing on it’s data to do the good job it does.
    - moonchild 5y ago
      Slug aa is only 1-dimensional. From the paper (end of section 2): > Adding and subtracting these fractions from the winding number has the effect of antialiasing in the direction of the rays. Averaging the final coverages calculated for multiple ray directions antialiases with greater isotropy, but at a performance cost. Considering only rays parallel to the coordinates axes is a good compromise, especially when combined with supersampling, as discussed later. I.E. you don't get a real 2-d coverage result, only an amalgamation of a number of 1-d coverage results; and you must trade off performance and quality. Other approaches do not require such a tradeoff. Analytic 2-d coverage can be done more cheaply than n 1-d samples (n is probably in the neighborhood of 4-6), and produces better (mathematically ideal, albeit with uncomfortable caveats) results. (Note 4-6 samples don't mean 4-6x slower, due to space partitioning, buffers, and other fixed costs, as well locality. And I think slug takes 2 samples by default as is.)
- danielvaughn 5y ago
  Oh I wasn’t pointing it out as a critical response to it being your thesis. I’m actually very interested to see how it turns out, because I’m digging into this space at the moment. I’m trying to build a platform-agnostic styling language specifically for UI/UX designers, and it’s leading me down the path of “render everything via WebGPU”. Is there a way I can follow your progress? Very keen on hearing more about your research if/when it’s ready.

marcan_42 5y ago

> which are programmed somewhat like regular computers but just with an astonishingly high number of threads. But they aren't that; they are actually wide vector processors, which means groups of threads need to be doing the same thing for it to perform properly! Branches and divergent control flow kill GPU performance. I'm sure you already know this, but I'm just pointing out for other folks reading. If GPUs were just CPUs with stupidly high core counts then things would be way easier, but it's more complicated than that.

derefr 5y ago
But any Turing-complete operation can be mapped mechanistically into a branchless ISA, can’t it? One of those “one-instruction” ISAs, for example, where every instruction is also a jump. Vector processors would compute on those just fine, just like they compute matrix-multiplication problem isomorphisms just fine. Or, for a more obvious/less arcane restatement: can't the shader cores just be given a shader that's an interpreter, and a texture that's a spritesheet of bytecode programs?
- Jasper_ 5y ago
  Yes, we can make GPU programs that render vector images this way, but they tend to be slower than an equivalent CPU program. Branches are not the problem, GPUs handle those just fine now actually. The problem is duplicated work. GPUs have cores that are individually much, much slower than a CPU, but make up for this by having lots and lots of them running in parallel. Having those cores all run the same serial interpreter does not give you increased parallelism, so the result is slower. Designing algorithms for the GPU requires rethinking your dataflow and structure to exploit the parallel nature of the GPU. GPUs are not just a "go fast" button.
  - derefr 5y ago
    Well, sure; but the problem of font rendering specifically is an "embarrassingly parallel" one, isn't it? If you've got 1000 glyphs at a specific visual size to pre-cache into alpha-mask textures; and you've got 1000 GPU shader cores to compute those glyphs on; then each shader core only needs to compute one glyph once. Can a CPU really be so much faster than these cores that it can run this Turing-complete font rendering program (which, to be clear, is already an abstract machine run through an interpreter either way, whether implemented on the CPU or the GPU) consisting of O(N) interpreted instructions, O(N) times, for a total of O(N^2) serial CPU computation steps; in less than the time it takes the O(N) GPU cores to run only O(N) serial computation steps each? Especially on a modern low-power system (e.g. a cheap phone), where you might only have 2-4 slow CPU cores, but still have a bounty of (equally slow) GPU cores sitting there doing mostly nothing? If so, CPUs are pretty amazing. But even if it were true that it'd be faster in some sense (time to first pixel, where the first rendered glyph becomes available?) to render on the CPU — accelerators don't just exist to make things faster, they also exist to offload problems so the CPU can focus on things that are its comparative advantage. Analogies: - An apprentice tradesperson doesn't have to be better at a delegated task than their mentor is; they only need to be good enough at the task to free up some time for the mentor to focus on getting something higher-priority done, that the mentor can do and the apprentice (currently) cannot. For example, the apprentices working for master oil painters did the backgrounds, so the master could focus on portrait details + anatomy. The master could have done the backgrounds faster! But then that time would be time not spent working on the foreground. - Ethernet cards. CPUs are fast enough to "bit bang" even 10GBe down a wire just fine; but except under very specific situations (i.e. dedicated network-switches where the CPU wants to process every packet synchronously as it comes in), it's better that they don't, leaving the (slower!) Ethernet MCU to parse Ethernet frames, discard L2-misdirected ones, and DMA the rest into kernel ring-buffer memory. - Audio processors in old game consoles like the SNES's S-SMP and the C64's SID — yes, the CPU could do everything these could do, and faster; but if the CPU had to keep music samples playing in realtime, it wouldn't have much time to do things like gameplay (which usually goes together with playing music samples!) Offloading font (or generalized implicit-shape) rendering to the GPU might not make sense if you're just computing letterforms for billboard textures in a static 3D scene (rather the opposite!) but in a game that wants to do things like physics and AI on the CPU, load times can likely be shorter with the GPU tasked with the font rendering, no? Especially since the rendered glyph-textures then don't have to be loaded into VRAM, because they're already there.