Gotcha's in programming

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Gotcha's in programming

Post by albinopapa » April 24th, 2019, 5:47 am

So a while back I posted a few 2D algorithms and decided I didn't like the interface, I wanted something a little more STL like...in other words, iterators. It isn't just to mimic the STL though, there's a purpose. I know they won't be fully compatible with the STL algorithms, but I'd like to at least be able to create a range based for loop using 2D containers, which is the easy part by the way. If you need to iterate over the entire set of containers, I'm done and have been done for some time. The issue comes when you want to iterate over a region of the 2D container.

1D iterators really don't need to store much more than the address they represent. They are very light weight and only have one value to compare for equality, the pointers. 2D iterators are proving a bit more complex and are quite a bit heavier.

I decided to use indexes instead of just a simple pointer. The reasoning behind this is someone or myself might have a vector of vectors where each element in the row vector is a row of data. I wouldn't be able to use pointer arithmetic. Another reason I chose indexes is to be able to return those indices to the user through the lambdas provided to the algorithms in case they are needed.

Well, when iterating over the entire container, the width constraints and stride of the container are the same, but in iterating over a region of the container, the width constraints and stride of the container are different. So, where to handle all the complexity? How to handle the differences?

As stated, the width constraints and container stride might be different, so my solution is to put the width and height of the region into the iterator. It also needs to know it's current position, so an X and Y value. It also needs a way to access the value at the current position when the user dereferences the iterator and so either store the stride and a pointer to the underlying array or just a pointer to the container and force the container to handle access since it knows it's own stride. I opted for the latter.

So the member list is:
container_pointer = 4/8 bytes depending on x86/x64
int x,y = (4+4) 8 bytes
int width, height = (4+4) 8 bytes
totaling: 20-24 bytes

Next issue is since there could be a difference in width and stride, and from my usage most of the time there is, the begin() function is always going to return an iterator with the full stride for the width, so even adding an offset to the iterator, it's not going to wrap the X position until it reaches the full stride of the container and not the region. Unless I plan on iterating over the entire container every time, I need to manually construct the iterators, which looks ugly.

Code: Select all

const auto beg_it = dim2d::const_index_iterator<dim2d::surface<Color>>( 10, 10, 50, 50, surface );

Code: Select all

const auto end_it = beg_it + dim2d::offset{ 0, 40 };  // stops when indices reach x = 10, y = 50
To me, figuring out the offset to add to beg_it takes a little mental gymnastic, more than needed anyway and is bound to be pretty error prone. Even just invoking the constructor for the end requires the same thought process.

Code: Select all

const auto end_it = dim2d::const_index_iterator<dim2d::surface<Color>>( 10, 50, 50, 50, surface );
I thought to myself "Okay, I'll create a 'surface_view' type container that makes it less error prone and a bit easier". I created surface_wrapper, which is overloaded to take a raw pointer, a reference and a const reference. The constructor takes a ( dim2d::offset, int width, int height, T container ). Now when I call begin() and end() I'll get the correct width initialized iterators, HOORAY!! Great, time to test...wait, now I need to dereference the position...!@#$%. Well, in the cases I am using a compatible container, I can just forward the position to it's overloaded subscript operator ( operator[] ), but the raw pointer one isn't going to have that option, so I guess I"ll need to add a stride member to it's constructor.

All this just to avoid having to type nested for loops every time I want to iterate over a 2D array.

My brain has been in a fog lately, so that may be what's been slowing me down or making this more complicated than it needs to be.

I could have just made an index class that takes those four inputs ( left, top, right, bottom ) and implement all the same behavior with the exception that dereferencing would just return the indices. The algorithms would be useless, but I'd be able to use ranged based for loops to iterate over the entire array or just a single for loop for regions and just use the current indexed position. Perhaps I'll still do that on top of the iterator and surface_wrapper setup for different purposes.

I haven't looked into the Ranges stuff that's suppose to come out in C++20, so I don't know how they will work.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Gotcha's in programming

Post by albinopapa » April 24th, 2019, 7:20 am

Here's an example of the dim2d::surface_wrapper for raw pointers and needing separate width and stride members:

Code: Select all

		auto dest = dim2d::surface_wrapper(
			dim2d::offset{ 0, 0 },
			gfx.pSysBuffer.columns(),
			screenRect.GetHeight(), 
			mappedSysBufferTexture.RowPitch / sizeof( Color ),
			reinterpret_cast< Color* >( mappedSysBufferTexture.pData ) );

		dim2d::copy( gfx.pSysBuffer.begin(), gfx.pSysBuffer.end(), dest.begin() );
I have taken the Graphics::EndFrame() code that looped from top to bottom and did a memcpy for each row and replaced it with the *dim2d::copy algorithm I made. For some reason instead of .width() and .height() member functions, I chose .columns() and .rows() to get the width and height of the compatible containers. In some machines, the back buffer isn't just screen width * sizeof( Color ). One machine I tested had a stride of 4,000 bytes, one machine had 4,096 bytes ( screen width = 800 ) while others were 3,200 as expected. So I need this to take that into account in cases where it iterates to 800, then needs to wrap back around to 0 instead of going until 1,000 or 1,024.

(*NOTE) Benchmarks have not been done, but I can ALMOST guarantee mine will be slightly slower. However, I have a little trick specifically in the dim2d::copy algorithm that checks if the types of both containers are trivially copyable, then basically do the same thing, loop from top to bottom, use memcpy to copy each row of data, so this part in particular should be equivalent.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

MrGodin
Posts: 721
Joined: November 30th, 2013, 7:40 pm
Location: Merville, British Columbia Canada

Re: Gotcha's in programming

Post by MrGodin » April 26th, 2019, 3:05 am

Thats a lot to digest Papa, you've come a long way, when ya gonna get a full on game going ;)
Curiosity killed the cat, satisfaction brought him back

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Gotcha's in programming

Post by albinopapa » April 26th, 2019, 4:16 am

Never I say.

I wish I could have the focus to do something like that, but turns out it's not what I enjoy. I enjoy the tool creation a bit more it seems.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Gotcha's in programming

Post by albinopapa » April 26th, 2019, 4:20 am

Honestly, sometimes I wonder what I'm doing with my life. I want to create something that someone will use, and so far I've come up short.

Chili gave me some advice a while back though that I haven't been doing. The advice was to use my tools to create something and then maybe people will get interested. Well, the closest thing was the extensions I made for the chili framework a while back had a user on here download and try it out, but haven't heard from him in a while. I'll be posting more stuff soon I hope along the lines of demos using the tools i'm working on. Right now, those gotchas I mentioned haven't been fully resolved.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Gotcha's in programming

Post by albinopapa » April 27th, 2019, 7:59 am

Holy fuck, that took way too long.

I was finally able to get the thing to work, though had to separate the raw pointer wrapper from the surface wrapper. Trying to shoehorn a single class to handle the two types was a nightmare.

I have a small demo of it working on my github page: chili_framework:main_branch

Ignore the other branches, they are from earlier revisions that's like a two years old...can't believe it's been so long.

You know what? Scratch that, the algorithms, iterators, and containers aren't even in that project, I have them referenced in that project, but they are in a separate folder...doh!

I am attaching the files if anyone is interested.

I have other containers coming, this was just what I have completed so far. I plan on making a static sized 2d array which I plan on using in a maze generator, I doubt I need a tone of cells for mazes.
I plan on a grid container, planned usage is 2D spatial partitioning.

The only thing I'm not liking is intellisense doesn't seem to like the template deduction guide for the dim2d::surface_wrapper class, but it compiles and runs as expected.
Attachments
dim2d.zip
dim2d algorithms, iterators and surface container and wrappers
(5.7 KiB) Downloaded 163 times
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply