I wasn't going to say anything, but you're being upmodded like crazy, so...
It's a complete apples to oranges comparison. Scribd is performing quite complex logic with an emphasis on correctness not speed. I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN.
I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN.
It is a nicely-written and illustrated article, but it describes a problem that hasn't been considered 'interesting' for decades and can, in any case, be tackled with a caching scheme. Why would they need to run the same intersection logic over and over, when there's only a finite number of glyphs to render in any given document?
> but it describes a problem that hasn't been considered 'interesting' for decades
Actually, polygon operations on grids is still an active research area, with the latest papers on the topic less than two weeks old: http://www.sci.utah.edu/socg2010agenda.html
> Why would they need to run the same intersection logic over and over [...]?
We usually don't. It basically depends on the context in which the glyphs appear on the page. For a standard, say, LaTeX document consisting of mostly text and without weird graphic operations taking place around or on top of the text, a given glyph is just processed once.
Absolutely. Modern graphics card hardware can easily process a few hundred million triangles per second. In all fairness, however, that has nothing to do with polygon intersection. Drawing a triangle on the screen with a z-buffer check is something quite different from actually computing an intersection polygon from two (multiply connected) input polygons.
CamperBob's flippant comment, however, got me thinking as to whether GPUs could be used to speed up this process, even if it were a bit.. "fuzzy." Anyone with GPU chops have any opinions on this?
Some modern GPUs support double precision floats, so accuracy would not be an issue. GPUs are practically built for this kind of computation, however there are probably two things holding them back:
1) GPU development requires specific developer experience. Making performant GPU code is an even nastier and less intuitive problem than making performant CPU code. A naive implementation would be shockingly inefficient.
2) Leasing GPU hardware in a datacenter is very rare. You'd have to do it at the office, or build your own servers and install them yourself at a colo. Lots of time and effort.
Even if the GPU solution was 10x faster (it could be much more, but it depends on how much the CPU, disk, network is a bottleneck), if you're talking about reducing $50k in computer time to $5k in computer time, it's almost certainly not worth it. If you're talking about $2m to $200k, that's a completely different matter.
Today relying on a GPU solution translates to vendor lock-in, it makes you much more dependent on a particular set of hardware and even a particular OS/driver stack.
I have had a small amount of success implementing GPGPU programs using webGL. If you code your solution to webGL you are able to offload OS/driver stack concerns to the web browser implementers.
That's really not true - we've been doing cloud GPU computing for a few years (all in OpenGL shaders and OpenCL) - we run in Windows, Linux, MacOS and on both NVIDIA and ATI.
We use GPUs for all of our computer vision and image processing, 10X is definitely a low-ball for what they're doing here - it would be much faster.
The important bit is at the end where they say "10% of the time is spent on polygon intersection" and the rest on image processing. We do GPU image processing on the cloud and this is (likely) where Scribd could likely obtain a significant speedup - many of our image processing operations run hundreds of times faster than on the CPU.
However, a modern game engine does perform a large number of polygon intersections for the purpose of collision detection. Of course, this is generally very rough for the purpose of performance.
It's a complete apples to oranges comparison. Scribd is performing quite complex logic with an emphasis on correctness not speed. I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN.