Back to General and Gameplay Programming

Linked list adventure

Bryan Wagstaff · 2017-02-10T21:38:49

Thanks for the reminder of why most of the civilized world has moved on from that sort of thing. I need to go attend to my eyes, they started bleeding reading that.

General and Gameplay Programming Programming

Started by Finalspace January 16, 2017 06:51 AM

57 comments, last by frob 7 years, 3 months ago

MarkS_

3,509

January 18, 2017 02:11 AM

You can leave memory non-initialized if you will be writing on it without reading from it.

I may allocate a large block of memory and leave it untouched then keep a counter saying there are 0 elements in use. The large block has unknown value, it is whatever it happens to be when it was allocated.

I can then write to cell 0 and increment the counter, there is now 1 element in use, the remaining block of memory is still garbage. Write a few more elements, increase the counter, and additional portions of the block have good values. Only the portions of the block that have been written to should ever be accessed, the rest is uninitialized and may point to anything.

It is fine to use that block of data without initializing it to a specific value. Maybe the OS zeroed it out for you before it was freshly assigned to you maybe it contained data from somewhere else in your process that was released, maybe it contains guard values from a debugging library. It doesn't matter what used to be in there, because your well-written code will only use portions of the memory that were written to with valid values.

Incidentally, this is also a common mistake for people who are unfamiliar with C++. Constructors don't write values to every data element, and they don't zero everything. The write values to the things that have values, including the vtable, and leave the rest as whatever happened to be there. Many containers are just fine initializing their size to zero and leaving the contained block untouched and uninitialized.

I get that, but that's not what I mean. He isn't leaving the object uninitialized. He is trying to initialize it with nothing, as though he is trying to initialize it to an uninitialized state. Uninitialized does not equal zero. I'm not understanding what he is trying to accomplish with the code he provided. This may be due to my lack of knowledge of C++.

https://en.wikipedia.org/wiki/Not_invented_here

I can see that as being a valid reason in certain circumstances. It helps ensure that you are not inadvertently stealing someone's IP, for example. However that isn't what he is trying to accomplish. He made it clear he is doing this due to his lack of understanding of what is going on behind the scenes of the STL library.

Oberon_Command

6,371

January 18, 2017 02:15 AM

You can leave memory non-initialized if you will be writing on it without reading from it.

I may allocate a large block of memory and leave it untouched then keep a counter saying there are 0 elements in use. The large block has unknown value, it is whatever it happens to be when it was allocated.

I can then write to cell 0 and increment the counter, there is now 1 element in use, the remaining block of memory is still garbage. Write a few more elements, increase the counter, and additional portions of the block have good values. Only the portions of the block that have been written to should ever be accessed, the rest is uninitialized and may point to anything.

It is fine to use that block of data without initializing it to a specific value. Maybe the OS zeroed it out for you before it was freshly assigned to you maybe it contained data from somewhere else in your process that was released, maybe it contains guard values from a debugging library. It doesn't matter what used to be in there, because your well-written code will only use portions of the memory that were written to with valid values.

Incidentally, this is also a common mistake for people who are unfamiliar with C++. Constructors don't write values to every data element, and they don't zero everything. The write values to the things that have values, including the vtable, and leave the rest as whatever happened to be there. Many containers are just fine initializing their size to zero and leaving the contained block untouched and uninitialized.

I get that, but that's not what I mean. He isn't leaving the object uninitialized. He is trying to initialize it with nothing. Like he is trying to initialize it to an uninitialized state. Uninitialized does not equal zero. I'm not understanding what he is trying to accomplish with the code he provided in the OP.

No, the syntax he's using is for zero initialization. See situation 2) in that link.

MarkS_

3,509

January 18, 2017 02:22 AM

No, the syntax he's using is for zero initialization. See situation 2) in that link.

I see. It is due to my lack of understanding. Still, wouldn't this only work if all of the member classes have default constructors defined? If the class I am trying to initialize to zero is just a class of integers or some such, then it should work without issue. However, if I'm trying to initialize a class of classes, then the result has the potential of being undefined, especially if raw pointers are thrown in the mix, correct?

frob

46,227

January 18, 2017 05:46 AM

Raw pointers has nothing to do with the mix.

A C++ class is effectively the same as a C struct, with some additional parts thrown in. One of those additional parts is called a vtable, which is a pointer to someplace configured by the compiler. Not all classes have them, but if they exist that pointer is absolutely essential to a created object. There are potentially other tidbits of data, but again they can be implemented as a single pointer. If you zero out that pointer with memset or a similar function, you break the data that is part of that object.

There is also some extra ways that data can be initialized, including constructors, initializer lists, value intializers, etc., where either values can be set directly or code can run to set the value.

If the class does not have that special pointer and if there are no special ways to initialize the data --- in other words, if it is "plain old data" or a POD type --- then the memory set can be zeroed out with memset or similar.

If the class does have the special pointer or if the class provides any of the various ways to initialize data the zeroing out the memory can cause undefined behavior. If you are lucky it will crash immediately, if you are unlucky the undefined behavior can lurk in the code for a long time as a ticking time bomb.

Finalspace

1,222

Author

January 18, 2017 07:08 AM

Okay, seems that the message got not through.

1. I am not saying C is the best way to create games, but for me its a better way than i was doing before (Before i used c++, c#, java, delphi and javascript).

2. Yes a linked list is never a all solving problem data structure.
If you want access the data by index, you are better use a array or something similar - something which is contiguous.
A linked list is not contiguos, so you will have to iterate over all items to find a specific one.

Sometimes a binary tree or a traditional tree is better, sometimes a simple queue, hash-table, index-table, etc. -> Wikipedia has all of it :D

But fastest is always a array, so i prefer using arrays when i can

3. The std library are fine, but it have its overhead (I made a performance comparison just to clarify that) - build and run the attached cpp file.
The analysis I made contains just the functions i need right now, so index read and write is not included!

Result on running that tool on two machines: Array is fastest, but do not support removal or pushing to front.
Second fastest is my naive linked list implementation I posted here.

Fast: Smallest amount of cpu cycles required for each operation.

4. With hash i mean just (y * width + x) which is just a 2D two 1D conversion - a hash index in my eyes.

5. Yes you was right, the dimension of the tilemap is insane and me forgot I already corrected it down to 2048^2 which is a lot more reasonable -> Sorry about that!

6. My Basic idea of that sparse tilemap is to define the entire tilemap as a index-table - directly accessing each element by its x and y - but allow negative positions, so you can draw to the left and to the top as well. In addition to iterate over the used tiles, i have two separated linked list: One for getting a tile from the pool, one for iterating over - thats it.

This works totally fine and seems to be run very fast, i can draw like crazy very big tilemaps.
Seems to be integrate great into my tile tracing algorythm as well ;-)

7. Enums start by 0 i know that, but for my physics contact Generation table i need to be sure to specify the exact index for each shape type in the enum, because there is only one contact generator registered, like for example: Box vs circle but not Circle vs box (low to high). Hard to explain without going in Detail.

Raw pointers has nothing to do with the mix.

A C++ class is effectively the same as a C struct, with some additional parts thrown in. One of those additional parts is called a vtable, which is a pointer to someplace configured by the compiler. Not all classes have them, but if they exist that pointer is absolutely essential to a created object. There are potentially other tidbits of data, but again they can be implemented as a single pointer. If you zero out that pointer with memset or a similar function, you break the data that is part of that object.

There is also some extra ways that data can be initialized, including constructors, initializer lists, value intializers, etc., where either values can be set directly or code can run to set the value.

If the class does not have that special pointer and if there are no special ways to initialize the data --- in other words, if it is "plain old data" or a POD type --- then the memory set can be zeroed out with memset or similar.

If the class does have the special pointer or if the class provides any of the various ways to initialize data the zeroing out the memory can cause undefined behavior. If you are lucky it will crash immediately, if you are unlucky the undefined behavior can lurk in the code for a long time as a ticking time bomb.

Exactly right. Thanks for that Explanation - this is the reason why i dont use any classes in my game.
I think the vtable is used for storing virtual function calls - to support abstraction / overrides.

My youtube channel: https://www.youtube.com/user/F1nalspace

Finalspace

1,222

Author

January 18, 2017 07:55 AM

Guys i have an idea. I am creating two sparse tile editors for you:

- One fully build with C++ with classes + std library
- Second written in plain C in the way i do

Both have can be compiled with fixed or dynamic memory architecture.

Everything - in the simplest possible way, no optimization whatsoever.

Platform: Win32 with OpenGL immediate rendering (No dependencies)
Compiler: VC++ 2015

-> I expect to be a noticable difference in performance and maintainability

My youtube channel: https://www.youtube.com/user/F1nalspace

sirpalee

761

January 18, 2017 08:06 AM

I checked your code, and compiled it on linux... (using c++11 chrono classes)

You are using STL classes incorrectly.

For example.

This


int *arr = (int *)calloc(sizeof(int), ARR_SIZE);

for (int i = 0; i < ARR_SIZE; i++) {
    arr[i] = rand();
}

Is not equal to


std::vector<int> list(ARR_SIZE);
for (int i = 0; i < ARR_SIZE; i++) {
    list.push_back(rand());
}

You'll get two completely different end results. The first one allocates an array, then overwrites the elements. The second one is allocating an array, then expanding the array with new elements.

A better comparison is.


std::vector<int> list(ARR_SIZE);
for (int i = 0; i < ARR_SIZE; i++) {
   list[i] = rand();
}

Also, were you compiling in release mode? As said earlier, in debug mode the STL contains extra checks, which is missing from your code. This is what I meant earlier by C++ code in comparisons usually doing more than the C code.

shaken, not stirred

Finalspace

1,222

Author

January 18, 2017 10:09 AM

I checked your code, and compiled it on linux... (using c++11 chrono classes)

You are using STL classes incorrectly.

For example.

This
int *arr = (int *)calloc(sizeof(int), ARR_SIZE);

for (int i = 0; i < ARR_SIZE; i++) {
    arr[i] = rand();
}
Is not equal to
std::vector<int> list(ARR_SIZE);
for (int i = 0; i < ARR_SIZE; i++) {
    list.push_back(rand());
}
You'll get two completely different end results. The first one allocates an array, then overwrites the elements. The second one is allocating an array, then expanding the array with new elements.

A better comparison is.
std::vector<int> list(ARR_SIZE);
for (int i = 0; i < ARR_SIZE; i++) {
   list[i] = rand();
}
Also, were you compiling in release mode? As said earlier, in debug mode the STL contains extra checks, which is missing from your code. This is what I meant earlier by C++ code in comparisons usually doing more than the C code.

- To be fair, an array do not have the ability to push things on - so it should not be included in that test, or changed so that the array items will be moved when pushed on. Thanks for that hint!

- Also true, that I just checked the result in DEBUG mode only - not release mode. But the results in release mode seems to be the same.

- True as well, i was assumed that std::vector(CAPACITY) allocates just the memory upfront, but starts at index 0 - so when i push things on, the capacity would not change. This assumtion was wrong, every push increases the capacity as well.

- About the additional checks STL does, I dont need it - should I care? In my game i use simple asserts for safety, but nothing more.

My youtube channel: https://www.youtube.com/user/F1nalspace

MarkS_

3,509

January 18, 2017 10:19 AM

I checked your code, and compiled it on linux...

Compiled just fine on Windows 10 and VS 2015 as well. Pretty much everything that he said gave an error compiled and ran just fine. :huh:

nesdavid

298

January 18, 2017 11:11 AM

Guys i have an idea. I am creating two sparse tile editors for you:

- One fully build with C++ with classes + std library
- Second written in plain C in the way i do

Both have can be compiled with fixed or dynamic memory architecture.

Everything - in the simplest possible way, no optimization whatsoever.

Platform: Win32 with OpenGL immediate rendering (No dependencies)
Compiler: VC++ 2015

-> I expect to be a noticable difference in performance and maintainability

I did that exercise once, but not in this forum. OOP vs Procedural (C++ vs C). OO tends to be bigger, more abstract and with more indirection than the other. Anyway you won't convince OOP heads to stop doing that, to many books, to many class hours, to many effort invested in something that is supposedly better than everything else.

If anyone is fluent in Spanish I did a talk in EVA (Argentinian GDC) about how OOP isn't the right tool for games.

Linked list adventure

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Linked list adventure

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines