Accidentally Quadratic

This is a quick one. I was recently working on an open source project of mine where I had to convert binary image data to a PNG. The project is written in Haskell, so I used the convenient library JuicyPixels. This allowed me to write the following code.

writeImageDataToPng :: [Word8] -> IO ()
writeImageDataToPng pixels = generateImage (generator pixels) width height

The generateImage function just takes the width and the height of the image, as well as a generator function of type Int -> Int -> Pixel. The generator function takes x and y coordinates and returns the pixel at those coordinates. Since my input is just a list of RGBA values, I implemented this function as follows.

generator :: [Word8] -> Int -> Int -> Pixel
generator pixels x y = Pixel r g b a
  where pixelIndex = ... -- some math based on x and y
        r = pixels !! pixelIndex
        g = pixels !! (pixelIndex + 1)
        b = pixels !! (pixelIndex + 2)
        a = pixels !! (pixelIndex + 3)

If you’re not familiar with Haskell, pixels !! n simply returns the value of pixels at index n. Easy enough, right? That’s what I thought, so I tested the function with a small 160x160 pixel image. To my surprise, it took almost 20 seconds to finish! Given the title of this post, you can probably already guess what the problem is. Even though [Word8] looks like an array and it’s possible to access elements by index, it’s very much not an array. In fact, it’s a linked list, and the indexed access is implemented simply by stepping through it. The documentation even warns you about the linear complexity of the !! operation.

After replacing the list with an actual array, the function now runs as quickly as expected :) It’s not the first time something ends up accidentally quadratic.