Re^4: Challenge: CPU-optimized byte-wise or-equals (for a meter of beer)

If you're working with 3-byte groups, that suspiciously sounds to me like you're treating RGB-data, and even if you're not, there is a crazy yet highly efficient (I believe) way of manipulating such data if you have the hardware (and software) to do it:

Using OpenGL and a chroma-key filter, you can "draw" the two strings over each other in parallel and then retrieve the resulting "image" from the massively parallel hardware again. It's not always certain that the parallelism you gain by offloading the work to the GPU outweighs the cost of transferring the data over the bus and the result back again, especially when benchmarked against the C versions you already have. See http://www.gpgpu.org/ for more information on the concept.

Comment on Re^4: Challenge: CPU-optimized byte-wise or-equals (for a meter of beer)

Replies are listed 'Best First'.
Re^5: Challenge: CPU-optimized byte-wise or-equals (for a meter of beer) by dragonchild (Archbishop) on Sep 13, 2007 at 12:49 UTC
Yes, I am treating RGB data. Specifically, I'm drawing the background PNGs for KayudaMaps. Unfortunately, since this is run on a server, I don't have a GPU (though that can be remedied if it's determined that it's worth it). The capability that this meter-of-beer is meant to give me is to overlay pictures with transparent bits on top of other pictures without having to use GL, ImageMagick, or Imager. It's not a rewrite of how any of those should do it - I'm just solving my specific problem in a very specialized manner. For example, since the images I'm working with don't have to be perfect, I've constrained my RGB values to 1-255, reserving 0 as transparent. The degradation is unnoticeable and I can handle transparent overlays without any speed penalties. This is also due to the fact that, for me, it's either fully transparent or fully opaque - another piece that specific to my problem that isn't generalizable to PNGs. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re^6: Challenge: CPU-optimized byte-wise or-equals (for a meter of beer) by Corion (Patriarch) on Sep 13, 2007 at 12:56 UTC
You can, of course, push the problem to the client by using CSS and transparency in the browser. But it's far nicer to do the processing server-side. My experience with OpenGL and GLSL has been very positive so far and I found the GLSL to be relatively readable and quite concise in formulating the process that I wanted to happen, as soon as I had a mental model of how the calculation I wanted to be done could be modelled as a single pass over an array. Maybe in the next 2 to 5 years, GPUs will become stock hardware, even without the graphics output, because they are incredibly suited to problems that can be formulated in an easily parallelizable way that reads from one or more memory sections and only write to one memory destination. But until then, you will be easier off by using the Inline::C version, especially in such one-off situations where it's likely that the bandwidth needed for uploading/downloading the image outweighs the performance gain of the (relatively simple) operation.	[reply]
Re^7: Challenge: CPU-optimized byte-wise or-equals (for a meter of beer) by dragonchild (Archbishop) on Sep 13, 2007 at 15:18 UTC
Pushing the problem out to CSS would be nice, but I'm working with thousands of calculations that are much easier to do server-side on strings of RGB triplets rather than client-side on full images. I ended up writing my own PNG outputer because I can do a huge amount of pre-processing because I'm controlling everything and can take advantage of specific optimizations. The browser can't do it because it has to deal with the general case. (Plus, IE's handling of PNG transparency isn't always correct.) I am looking forward to a time when GPUs will be more common. It would be interesting to see if CPUs could be replaced by GPUs for certain kinds of programming needs. I wonder if a gcc target could be a GPU ... My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re^5: Challenge: CPU-optimized byte-wise or-equals (for a meter of beer) by szbalint (Friar) on Sep 13, 2007 at 08:03 UTC
That sounds like what I've been doing to solve a similar problem when I wanted to compute influences (in a 2D environment, with influences radiating out in a given radius from a given pixel, and finding the strongest for any given point). I've achieved a 500x speedup using gpgpu solutions compared to solving it in a purely CPU based way. Of course, it took longer to write and it needs capable hardware (vertex and fragment shaders are used), but it's fast.	[reply]