Can I draw a square with pixels more efficiently?

Question

I'm drawing a square on a window using an implementation of Xlib. I put a colored pixel with my_pixel_put at a specific (x,y) coordinate.

Code to review

#define LWST_VAL 200
#define HGHST_VAL 400

int     main()
{
    t_data  img; //image data
    int x = LWST_VAL, y = LWST_VAL;

    // steps creating a window, creating an image
    while (x >= LWST_VAL && x <= HGHST_VAL)
    {
        while ((y > LWST_VAL && y < HGHST_VAL && (x == LWST_VAL || x ==
            HGHST_VAL)) || y == LWST_VAL || y == HGHST_VAL)
        {
            my_pixel_put(&img, x, y, 456);
            y++;
        }
        if (x > LWST_VAL && x < HGHST_VAL && y == (LWST_VAL + 1))
            y = HGHST_VAL;
        else
        {
            y = LWST_VAL;
            x++;
        }
    }
    // steps pushing image to the window, keep the window open
}

Output

Question

Could anything improve the performance of my code ? Or its readability ?

Any feedback appreciated.

Edit

This is the prototype of my_pixel_put :

void    my_pixel_put(t_data *img, int x, int y, int colour)

img is a structure containing data about the image such endiannes, bits per pixel, ... x and y are the width and height of the window. colour is the RGB colour of the pixel. (0,0) is actually the top left corner of the window (I know don't ask me why).

Answer 1

Disclaimer

I don't have a working C compiler on my work computer, nor do I have Xlib available to me (I'm also not familiar with it, at all). That being said, given that we know our image is a square, you can do this with a single loop.

Use a simpler algorithm

The basic idea is that we know each corner of our square, and then by stepping through the length of a side, we can draw a pixel on each side of the square per iteration. This way, instead of nested looping, you do it all at once.

// assuming a coordinate system where 0,0 is the bottom-left corner of the image
// starting at each corner, draw the corresponding clock-wise line
for (int pos = LWST_VAL; pos <= HGHST_VAL++pos)
{
    // The bottom line
    my_pixel_put(&img, pos, LWST_VAL, 456);
    // The top line
    my_pixel_put(&img, pos, HGHST_VAL, 456);
    // The left line
    my_pixel_put(&img, LWST_VAL, pos, 456);
    // The right line
    my_pixel_put(&img, HGHST_VAL, pos, 456);
}

Cache behavior

The one thing that occurs to me about this implementation is that you might not do quite as well from a caching perspective - the one benefit of doing things on a side-by-side basis is that you're more likely to be operating on data from the cache instead of from memory. I don't know how &img is actually stored or what my_pixel_put is doing, so its hard to give more concrete advice about this.

If you did encounter caching issues, short of changing things to process side-by-side (or maybe top + bottom in one loop, and left + right in another), there isn't a whole lot to do. A normal technique to handle cache churn is to use blocking to break up the loop. That won't help here, unfortunately - see below for why.

Suppose we know the following (these numbers are made up):

• 16 lines of data can be held in the cache
• 4 integers can be held in the cache at the same time
• img is a matrix stored as a row-wise vector, and my_pixel_put effectively becomes img[WIDTH * y + x] = 456
• img is aligned such that the left-most side of the square represents the start of a cache line (there will be many cache lines to get to the right side)

Each iteration of our loop grabs 4 cache lines - one for each side of the square. The top and bottom will be able to re-use the cache line for the next three values, while the right and left will have to get a new cache line. We then have the following sequence for how many cache lines we get at a time:

1. 4
2. 6
3. 8
4. 10
5. 14
6. 16
7. etc

The 7th loop iteration would force some of the old data out of the cache. If we were going to be using data besides the border of the square (e.g. by filling it somehow) then it would be worthwhile to operate on 6x6 "blocks" of data, because then everything is in-cache instead of in-memory. Because we aren't using the interior of the square, however, we'll never actually get a benefit to blocking up the operation - most of those cache lines will always go to waste

Parallelization

Another benefit of this is that, if you wanted to parallelize this on a CPU or port it to a GPU, it'll be more straightforward. On a CPU, this is an embarrassingly parallel problem - assuming that my_pixel_put is thread-safe as long as you aren't modifying the same pixel, threading it should be trivial. On a GPU, the lack of conditional operations makes it a breeze as well.

You may want to change your memory access patterns if you go parallel, but additional detail is left as an exercise for the reader. As a hint, for CPU-based parallelism each thread should generally be working on distinct pieces of work to avoid ruining cache coherence.

Looking at your code as written, without algorithm changes

Reviewing your actual code, there are some simple ways that you can improve readability & maintainability without changing the algorithm much.

1. I don't like your outer while loop - you basically just have a for loop, with some extra weirdness about the top vs bottom line.
2. I have a very similar beef with your inner while loop - this one is even more obviously just a for loop.
3. Some of your conditions that you pack into your while should be separate, if only for readability's sake. Several of them are obviously removed by switching to a for loop, while others are better suited as an if statement wrapping your loop.
4. Your macro names are unnecessarily mangled - its okay to have vowels in your macros
5. Is it really necessary to have these be macros?

for (int x_position = LWST_VAL; x_position <= HGHST_VAL; ++x_position) 
{
    if (x_position == LWST_VAL || x_position == HGHST_VAL) {
        for (int y_position = LWST_VAL; y_position <= HGHST_VAL; ++y_position) 
        {
            my_pixel_put(&img, x_position, y_position, 456);
        } 
    } else {
        my_pixel_put(&img, x_position, LWST_VAL, 456);
        my_pixel_put(&img, x_position, HGHST_VAL, 456);
    }
}

Whoops, I ended up rewriting it more than I meant to - I just couldn't make myself add another loop just because. To keep an equivalent number of loops, you could do something like this:

for (int side_count = 0; side_count < 2; ++side_count) {
    for (int x_position = LWST_VAL; x_position <= HGHST_VAL; ++x_position) 
    {
        if (side_count == 0 && (x_position == LWST_VAL || x_position == HGHST_VAL)) {
            for (int y_position = LWST_VAL; y_position <= HGHST_VAL; ++x_position) 
            {
                my_pixel_put(&img, x_position, y_position, 456);
            } 
        } else {
            my_pixel_put(&img, x_position, side_count == 0 ? LWST_VAL : HGHST_VAL, 456);
        }
    }
}

Answer 2

The real performance issue here is fairly simple: good performance is obtained by not repeating steps. The big step that you are doing repeatedly is to figure out where the pixel goes in the output space.

If we consider @Dannano's

img[WIDTH * y + x] = 456;

We wind up doing that currently for every point. Multiplication is hard (at least classically, and still on simple machines), so the fewer times we do it, the better. Consider this function:

static void my_primitive_line_draw(pixel_t *ptr, size_t stride, unsigned count, pixel_t color)
{
    while (count--) {
        *ptr = color;
        ptr = (pixel_t*) ( ((char *)ptr) + stride );
        /* or maybe:
        ptr += stride;
        */
    }
}

Given a starting location and an appropriate stride, this can draw a vertical, horizontal, or 45 degree diagonal. Note that this should not be publicly accessible. It is too screwy if given the wrong parameters. But called from my_line_draw(image_t, int x0, int y0, int x1, int y1, pixel_t color) it provides a high performance implementation. FYI: Good values for stride are ((-WIDTH, 0, or +WIDTH) + (-1, 0, or +1)) * sizeof(pixel_t) (and omit the sizeof if you use the "or maybe" clause).

The other thing that tends to be pricy is all the validation needed. For instance, your my_pixel_put() must validate: the image is valid, the x is in a legal range, the y is in a legal range, and the color is valid. But an internal function like my my_primitive_line_draw() can be called with known good parameters. So my_line_draw() must still do it, but only once per line.

There are a number of similar tricks for high performance rendering of more complex shapes, though they tend to only work on well conditioned shapes.

---

Having said all that, one other performance issue in your code is that convoluted looping structure. Just write two independent loops, one on x, in which you draw at x,LWST_VAL and x,HGHST_VAL, and a similar one on y.