Just wanted to point out, as is typical with whiteboard questions, there's a small indexing error that's hard to spot unless you know a few easy edge cases to check. FromMinY and FromMaxY would be the same and you would skip the outer for loop entirely even if FromMinX and FromMaxX were different.
It's the classic: if you have books 2 through 5 of a series you have 4 books problem.
Love the content though, it's really interesting to see what interview questions back in 1994 looked like.
That's not how rectangles work in graphics. The "max" value is never included in the rectangle, because you want the ability to specify abutting rectangles with no gap which do not both write to the same row/column. So by convention, all intervals are "min included, max not". This becomes very important in float.
You can see this, for example, stated in the description of Windows' own API:
Crap... Even when working with float rectangles in my own code, I've never adopted this max-exclusive convention. I probably need to go check all of those now...!
Yeah, I did not do a good job with the diagram at all :( I should have drawn it differently so that I showed where the two lines were, and put one after the XMax. If I redo the video at some point I will do it right!
1) Wouldn't calling memcpy instead of having an inner loop be more concise?
2) Let's say your buffer width was something like 2160 and your rectangle had a width of 2000. Is there any performance benefit potential from using something like memcpy?
3) In an interview, it feels like they often want you to think about the edge cases. In this case, I would point out the possibility that the rect from the source buffer might be too large for the destination buffer and position. This solution wouldn't handle that intuitively.
1) It would be much more expensive to invoke a function call there, unless you are expecting a compiler to generate it inline for you, but the compilers that do that will generally turn memory copies into a memcpy automatically (unfortunately sometimes, since in the case of any small rectangle, it is a net loss to do so).
2) Usually not, although if you were trying to be performant, you would not use memcpy anyway, you would include the proper AVX code to do full 32- or 64-byte copies. There is no need to add the overhead of memcpy because you usually know things about the buffer that memcpy does not.
3) You can tell they did not expect you to do that because you are not passed the bounds of the buffers. If you were, though, extending this code to handle this is trivial: you just min/max the bounds before copying. The loops stay exactly the same.
I guess I would hope that memcpy isn't copying over byte by byte. Since, before you even get to AVX, you could do at least 8 bytes at a time these days. I guess this is an area where you should just have total faith in the compiler to do the right thing? If so, do you think the compiler has an easier time reasoning with the code as you wrote it or with memcpy?
There are a lot of misconceptions about memcpy that people have, I think because of bad YouTube videos in the past :) Compilers automatically generate larger copies for you:
You do not need to call memcpy to have this happen. Mostly what you get if you actually call memcpy (as opposed to the compiler recognizing it and actually doing generating the code in-line) is a bunch of setup overhead that is not specialized to the task at hand. For example, you might end up with something bad like this:
Oh wow. I actually do find that pretty shocking. Any idea why your for loop and memcpy would be interpreted differently by the compiler? Is the idea not conceptually the same thing? It feels like memcpy could not be more explicit about the authors intentions.
Well, loops in general will be unrolled and vectorized by CLANG, so that's just what you would expect to happen. In order to get it to that with memcpy, you would have to first make sure it was going to use a builtin version of that, so it knew what it was - which honestly I thought it did by default, but maybe I am wrong about that? There may be some additional compiler switches you could add to make it do that... since I never rely on builtin memcpy/memset I am not sure what they would be.
Typically this wouldn't make much sense, because you're not guarding against a Y overrun. Usually you just do min/max of the rectangle with a clipping rectangle first, then call this function.
I made exactly like you did "max not included" (range [min, max)). Then while writing checks for making sure that min coord is < max coord I decided to do something useful instead of bailing out. I implemented copy backwards from source, so you can flip rectangle X or Y or both if you swap min and max in arguments. But then this "max not included contract" became non intuitive. Which border is not included, the one that is bigger or the one that is on "max" argument place?
I ended up changing `x_min`, `x_max` to just `x0`, `x1` and made the range inclusive.
Now I wonder if it would be better to keep [min, max) range and add a flip flag instead :)
Shouldn't there be a `+1` on both of those to match the way you wrote the for loops? Or the for loops should have `<=` instead of `<`, either way would work.
Potentially your answer is in Casey's response to another question on this post. Which is that maxes, in this case, are exclusive. The range for this scenario is [5,10), not [5,10]. Which, in my experience, is common for many APIs.
Yes. I should've said this in the video, but I am so used to the graphics interval convention that it never even occurred to me. But obviously non-graphics people would be confused by this, because there is no obvious reason why you would include one bound and not the other!
Makes total sense, yes. Had I thought of it, I would have explained this on the lightboard, it's just such a force of habit now, I never think of it :(
I find this convention everywhere. Right boundary is usually not included in algorithms, so you can do stuff like `foo(begin, begin + size)` without adjusting size;
The same goes for all STL stuff. end points past the buffer and is never included in the computation
Just wanted to point out, as is typical with whiteboard questions, there's a small indexing error that's hard to spot unless you know a few easy edge cases to check. FromMinY and FromMaxY would be the same and you would skip the outer for loop entirely even if FromMinX and FromMaxX were different.
It's the classic: if you have books 2 through 5 of a series you have 4 books problem.
Love the content though, it's really interesting to see what interview questions back in 1994 looked like.
That's not how rectangles work in graphics. The "max" value is never included in the rectangle, because you want the ability to specify abutting rectangles with no gap which do not both write to the same row/column. So by convention, all intervals are "min included, max not". This becomes very important in float.
You can see this, for example, stated in the description of Windows' own API:
https://learn.microsoft.com/en-us/windows/win32/api/winuser/nf-winuser-fillrect
This is so ingrained in my head that I didn't even think to mention it!
- Casey
Crap... Even when working with float rectangles in my own code, I've never adopted this max-exclusive convention. I probably need to go check all of those now...!
Oh that makes more sense! I'm used to that with array slices from Python but the picture in the video threw me off so I thought it worked differently.
Yeah, I did not do a good job with the diagram at all :( I should have drawn it differently so that I showed where the two lines were, and put one after the XMax. If I redo the video at some point I will do it right!
- Casey
1) Wouldn't calling memcpy instead of having an inner loop be more concise?
2) Let's say your buffer width was something like 2160 and your rectangle had a width of 2000. Is there any performance benefit potential from using something like memcpy?
3) In an interview, it feels like they often want you to think about the edge cases. In this case, I would point out the possibility that the rect from the source buffer might be too large for the destination buffer and position. This solution wouldn't handle that intuitively.
1) It would be much more expensive to invoke a function call there, unless you are expecting a compiler to generate it inline for you, but the compilers that do that will generally turn memory copies into a memcpy automatically (unfortunately sometimes, since in the case of any small rectangle, it is a net loss to do so).
2) Usually not, although if you were trying to be performant, you would not use memcpy anyway, you would include the proper AVX code to do full 32- or 64-byte copies. There is no need to add the overhead of memcpy because you usually know things about the buffer that memcpy does not.
3) You can tell they did not expect you to do that because you are not passed the bounds of the buffers. If you were, though, extending this code to handle this is trivial: you just min/max the bounds before copying. The loops stay exactly the same.
- Casey
I guess I would hope that memcpy isn't copying over byte by byte. Since, before you even get to AVX, you could do at least 8 bytes at a time these days. I guess this is an area where you should just have total faith in the compiler to do the right thing? If so, do you think the compiler has an easier time reasoning with the code as you wrote it or with memcpy?
There are a lot of misconceptions about memcpy that people have, I think because of bad YouTube videos in the past :) Compilers automatically generate larger copies for you:
https://godbolt.org/z/oYYrv9vfY
You do not need to call memcpy to have this happen. Mostly what you get if you actually call memcpy (as opposed to the compiler recognizing it and actually doing generating the code in-line) is a bunch of setup overhead that is not specialized to the task at hand. For example, you might end up with something bad like this:
https://godbolt.org/z/nrz9YzTnv
which you DEFINITELY do not want.
- Casey
Oh wow. I actually do find that pretty shocking. Any idea why your for loop and memcpy would be interpreted differently by the compiler? Is the idea not conceptually the same thing? It feels like memcpy could not be more explicit about the authors intentions.
Well, loops in general will be unrolled and vectorized by CLANG, so that's just what you would expect to happen. In order to get it to that with memcpy, you would have to first make sure it was going to use a builtin version of that, so it knew what it was - which honestly I thought it did by default, but maybe I am wrong about that? There may be some additional compiler switches you could add to make it do that... since I never rely on builtin memcpy/memset I am not sure what they would be.
- Casey
If `dst_min_x + width > dst_pitch` you end up writing to dst not in a rectangular shape any more.
I wonder if they expected you to write some checks or to suggest changing API for a more "defensive" programming style.
Typically this wouldn't make much sense, because you're not guarding against a Y overrun. Usually you just do min/max of the rectangle with a clipping rectangle first, then call this function.
- Casey
I made exactly like you did "max not included" (range [min, max)). Then while writing checks for making sure that min coord is < max coord I decided to do something useful instead of bailing out. I implemented copy backwards from source, so you can flip rectangle X or Y or both if you swap min and max in arguments. But then this "max not included contract" became non intuitive. Which border is not included, the one that is bigger or the one that is on "max" argument place?
I ended up changing `x_min`, `x_max` to just `x0`, `x1` and made the range inclusive.
Now I wonder if it would be better to keep [min, max) range and add a flip flag instead :)
int Width = FromMaxX - FromMinX;
int Height = FromMaxY - FromMinY;
Shouldn't there be a `+1` on both of those to match the way you wrote the for loops? Or the for loops should have `<=` instead of `<`, either way would work.
If FromMaxX is 10 and FromMinX is 5.
```
for(int i = FromMinX; i < FromMaxX; i++) {}
```
Runs on indices [5,6,7,8,9] or 5 times.
Potentially your answer is in Casey's response to another question on this post. Which is that maxes, in this case, are exclusive. The range for this scenario is [5,10), not [5,10]. Which, in my experience, is common for many APIs.
Yes. I should've said this in the video, but I am so used to the graphics interval convention that it never even occurred to me. But obviously non-graphics people would be confused by this, because there is no obvious reason why you would include one bound and not the other!
- Casey
Well, I was going from the drawing in the video where you showed the bottom-right coordinates as being part of the rectangle, not outside of it.
This is what I mean: https://youtu.be/ielZBraKsw8?t=296
Makes total sense, yes. Had I thought of it, I would have explained this on the lightboard, it's just such a force of habit now, I never think of it :(
- Casey
I find this convention everywhere. Right boundary is usually not included in algorithms, so you can do stuff like `foo(begin, begin + size)` without adjusting size;
The same goes for all STL stuff. end points past the buffer and is never included in the computation