Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

besides, map.get(x,y) isn't all that complex compared to

Code: [Select]

map[x][y].

You can do better, because () can be overloaded on the whole class:

map(x,y)

although it's an implementation detail that really shouldn't make a difference.

Well it will, because of memory caching. If you are processing a whole map, then you should do so with the "grain" of memory, rather than against the grain to take advantage of caching. That can mean a 10-20x speedup between implementations, and the only difference is whether you put the x-loop on the outside or the y-loop. People trust the magic of the "compiler optimizations", but the compiler doesn't do all the things that people think it does. If you e.g. have a useless variable used in an inefficient way, the compiler leaves that variable in place doing the job you told it to do - it's not a magic "shitty code fixing genie". A lot of "proper" OO ways of doing things are super-inefficient, in ways that compilers can't fix.

Bools are basically the worst data type in the world to put in a class for example. If you have an int, a bool and then an int. Then the bool will take up 4 bytes, because the compiler needs to align the next int on a 4-byte boundary to allow for faster memory access. That's the "optimization" it makes to handle the shitty memory layout you specified. But those bools and their padding end up making data structures much bigger, so you can't load as many of them as possible per memory-cache-read. So, e.g. the very worst thing you could do would be to stick a "bool active" in the middle of a data structure, then cycle through all data structures and only do an action to the "active" ones. Huge amount of wasted space with padding, and with memory cache reading of ALL the data from each and every game object in the array. The faster and more memory efficient system would be to instead have a separate "active" array of bools, cycle through that and then only load the actual data structures for the "active" ones.

So, yeah, over-object-orienting things is like normalizing databases to 4th normal form. It's good on paper, but leads to an inefficient clusterfuck.

[lethosor]

Good point about the "grain". I just meant that the way the data is ordered internally shouldn't make a difference with how it's accessed externally. I'm not entirely convinced one way or the other is better for a 2D map if it's randomly accessed, but for things that do loop over the entire map, going with the grain is a good idea.

I do know about padding, but I don't think that's something you can blame OOP for. The same is true nearly anywhere you're storing data types of different sizes next to each other. A bool and int declared on the stack can also have 3 bytes of padding between them. Memory-inefficient code is usually attributable to people who don't understand memory efficiency, not necessarily people who use OOP inappropriately (although there is overlap between the two, I'll admit).

[Reelya]

The same is true nearly anywhere you're storing data types of different sizes next to each other.

But when do you do that in a non-OO context? Prior to C++ people might have used structs to achieve that, but I'd say they were applying "primitive OO thinking" when doing so. OO formally promotes the practice of encapsulating data by "Object", making it much more prevalent to cluster the data in that particular way. A raw non-OO language encourages the exact opposite: you use arrays of homogenous data types, and the index into each array specifies which entity you're dealing with.

OO thinking also encourages people to be hardware agnostic, even if they have exactly one target platform. I dealt with idiots like this when I did my degree: OO zealots who'd absorbed the lessons too well and refused to ever pin down the physical specifications because "OO says you should never worry about the implementation details". To them, having elegant UML is more important than a system that works well.

[Spehss _]

Bools are basically the worst data type in the world to put in a class for example. If you have an int, a bool and then an int. Then the bool will take up 4 bytes, because the compiler needs to align the next int on a 4-byte boundary to allow for faster memory access. That's the "optimization" it makes to handle the shitty memory layout you specified. But those bools and their padding end up making data structures much bigger, so you can't load as many of them as possible per memory-cache-read. So, e.g. the very worst thing you could do would be to stick a "bool active" in the middle of a data structure, then cycle through all data structures and only do an action to the "active" ones. Huge amount of wasted space with padding, and with memory cache reading of ALL the data from each and every game object in the array. The faster and more memory efficient system would be to instead have a separate "active" array of bools, cycle through that and then only load the actual data structures for the "active" ones.

Good point about the "grain". I just meant that the way the data is ordered internally shouldn't make a difference with how it's accessed externally. I'm not entirely convinced one way or the other is better for a 2D map if it's randomly accessed, but for things that do loop over the entire map, going with the grain is a good idea.

I do know about padding, but I don't think that's something you can blame OOP for. The same is true nearly anywhere you're storing data types of different sizes next to each other. A bool and int declared on the stack can also have 3 bytes of padding between them. Memory-inefficient code is usually attributable to people who don't understand memory efficiency, not necessarily people who use OOP inappropriately (although there is overlap between the two, I'll admit).

...So, is it a good idea to have bools in classes or not? I'm curious since I'm using a bool in a class used in my dungeon generation project and I'd like to know before I do any more work on it and get too reliant on the bool to remove it without needing to rewrite a bunch of code. I could probably just replace the bool with an int since 0 and any non-zero works as well for true/false conditions.

[Gentlefish]

Bools are basically the worst data type in the world to put in a class for example. If you have an int, a bool and then an int. Then the bool will take up 4 bytes, because the compiler needs to align the next int on a 4-byte boundary to allow for faster memory access. That's the "optimization" it makes to handle the shitty memory layout you specified. But those bools and their padding end up making data structures much bigger, so you can't load as many of them as possible per memory-cache-read. So, e.g. the very worst thing you could do would be to stick a "bool active" in the middle of a data structure, then cycle through all data structures and only do an action to the "active" ones. Huge amount of wasted space with padding, and with memory cache reading of ALL the data from each and every game object in the array. The faster and more memory efficient system would be to instead have a separate "active" array of bools, cycle through that and then only load the actual data structures for the "active" ones.

Good point about the "grain". I just meant that the way the data is ordered internally shouldn't make a difference with how it's accessed externally. I'm not entirely convinced one way or the other is better for a 2D map if it's randomly accessed, but for things that do loop over the entire map, going with the grain is a good idea.

I do know about padding, but I don't think that's something you can blame OOP for. The same is true nearly anywhere you're storing data types of different sizes next to each other. A bool and int declared on the stack can also have 3 bytes of padding between them. Memory-inefficient code is usually attributable to people who don't understand memory efficiency, not necessarily people who use OOP inappropriately (although there is overlap between the two, I'll admit).

...So, is it a good idea to have bools in classes or not? I'm curious since I'm using a bool in a class used in my dungeon generation project and I'd like to know before I do any more work on it and get too reliant on the bool to remove it without needing to rewrite a bunch of code. I could probably just replace the bool with an int since 0 and any non-zero works as well for true/false conditions.

Are you using java? Given the example above, it would be easy enough to give a static ID to the class, and have each generation of an object increment ID and give it to themselves as objID, then shove each generated object (by ID) into the "active" array.

[Reelya]

...So, is it a good idea to have bools in classes or not? I'm curious since I'm using a bool in a class used in my dungeon generation project and I'd like to know before I do any more work on it and get too reliant on the bool to remove it without needing to rewrite a bunch of code. I could probably just replace the bool with an int since 0 and any non-zero works as well for true/false conditions.

If your code isn't time-critical or there aren't going to be zillions of those objects accessed frequently, or you're likely to rewrite it before needing to scale it up, then it won't be worth worrying about. Let me cite from Intel directly about how memory alignment works:

https://software.intel.com/en-us/articles/coding-for-performance-data-alignment-and-structures

Every data type has an alignment associated with it which is mandated by the processor architecture rather than the language itself. Aligning data elements allows the processor to fetch data from memory in an efficient manner and thereby improves performance. The compiler tries to maintain these alignments for data elements to provide optimal performance.
...
In general, the compiler will try to fulfill these alignment requirements for data elements whenever possible. In the case of the Intel® C++ and Fortran compilers, you can enforce or disable natural alignment using the –align (C/C++, Fortran) compiler switch. For structures that generally contain data elements of different types, the compiler tries to maintain proper alignment of data elements by inserting unused memory between elements. This technique is known as 'Padding'. Also, the compiler aligns the entire structure to its most strictly aligned member. The compiler may also increase the size of structure, if necessary, to make it a multiple of  the alignment by adding padding at the end of the structure. This is known as 'Tail Padding'. Thus padding improves performance at expense of memory.

e.g. if you have an 8-byte long value after a char/bool, the compiler inserts 7 bytes of wasted space in between (padding). There's also tail padding to increase the size of the total struct to a multiple of the size of the largest element. e.g. an 8-byte long or double means the entire data structure will be padded to a multiple of 8 bytes if it's not already.

Minimizing memory wastage: One can try to minimize this memory wastage by ordering the structure elements such that the widest (largest) element comes first, followed by the second widest, and so on.

So you can do that first, which will minimize padding without changing anything logically. After that, you can work out exactly how many bytes your data struct is still taking up, and you can tweak things if it's slightly over alignment by e.g. ensuring ints are sized to only what's needed, or packing multiple bools into a char, and making a lookup function that does bit masking. If you can get your data structure to a power of two in size, you'll have the highest possible efficiency since the CPU can now load an integer number of structures from memory per memory cache read.

[Gentlefish]

...Wow, that's nice.

[Reelya]

The other thing that I didn't mention from that article is the use of __declspec. __declspec tells the compiler to align a structure in memory to a specific boundary.

e.g. if you have a structure full of ints, then by default, the compiler will align objects to the nearest 4 byte memory address. But cache lines are 64 bytes, so e.g. a structure of 16 ints would have a very low chance of actually being aligned to a single cache line, meaning all random accesses require two reads per object. If you tell declspec to align that structure to 64 bytes, it ensures each object takes up an exact cache line, effectively doubling the speed. Also if cache alignment was ad-hoc, and sometimes your data did and didn't become aligned just by chance, then that could explain why sometimes you get "fast" runs on a program and other times it's a lot slower "just because". I know I've experienced that. Using the compiler to ensure predictable cache alignment helps to ensure predictable performance.

Clearly, you can get the best benefit if you can align your structures to some simple fraction of 64 bytes: 64, 32, 16. Though other fractions such as 48 could be better than nothing if packed into memory: only 1 in three of the data structures would cross two cache lines.

[Spehss _]

Getting a compiler error for redefinitions of functions. No idea what I'm doing wrong or how to fix it. The error involves all the functions of diceroller.h

I initially only had all the diceroller functions in an h file, which I think is not really how I'm supposed to organize functions, but it worked in the past and I never got around to changing it.

Error came up as I tried adding functions to Map class, separated into a source file. The functions would need to use functions from diceroller and not #including the diceroller files resulted in errors for undefined functions. After adding the #include to Map.h I started getting the duplicate function errors.

[snip]

Anyone see what I'm doing wrong?

I'm searching google and it may be an issue with the IDE and how it handles files in projects. According to other people on the internet, Code::Blocks "automatically includes" files added to the project and manually #including those same files causes issues. That sounds like bullshit, removing the include statements in main from files added to the project results in errors due to undefined code contained in those files.


Figured it out. Added the cpp source files to the Code::Blocks project. This just reminds me I have very little idea of what I'm doing when it comes to using an IDE.

[Reelya]

your mistake is including cpp files. That's not how it's meant to work

.cpp files contain the implementations, .h files contain the specifications. You only use include for .h files. This is not enforced at all, but it's just a convention people have settled on. #include merely embeds one file inside another using blind cut and paste. So it clones whatever you included, meaning you now have two copies of that cpp in the system.

#include really is just a "cut and paste" operation. e.g. this will actually work:

main.cpp :

printf(
#include "hello.h"
);

hello.h :
"Hello World"

And whatever other stupid stuff you can think up.

[Spehss _]

Yeah, I got it. Deleted the #include statements w/ cpp files, and added the cpp and h files of all the involved files to the codeblocks project. Don't know why it works now but it does.

[Reelya]

cpps hold the actual data, .h files only hold descriptions. That's why it works. You can have multiple descriptions of something in the system, but you can't have more than one actual thing with the same name.

e.g. consider cpp files like a house, and .h files like the phone book. Each house "exists" in the phone book, and every house "includes" the entire set of addresses in the phone book. But there can never be two houses which are at the same actual address, not matter how many phone books you print. This is pretty much exactly how the cpp/h breakdown works. cpp files hold stuff and you can't have two things with the same name. .h files hold references to stuff, and you can refer to stuff as many times as you like.

It's similar with objects - a .h file can hold the description of a class, and this is copied to all cpp files which include that .h file. e.g. each cpp file could end up with a description of "Cat", and these descriptions can be shared or replicated (unless one description contradicts another in which case you get an error). But "Bob the cat" is a thing, not a description, so it can only exist once. This is also the reason that you have to declare static class variables outside the class itself: they are individual things rather than shared descriptions, so they have to be specified exactly once in a file that's not shared.

[MorleyDev]

...So, is it a good idea to have bools in classes or not?

In 99% of cases that'll be overkill and could potentially interfere with compiler optimisations and so actually result in worse performance. Following recommended clean coding patterns until empirical evidence suggests a reason to stray from them is recommended for most situations. A bool is very clear to both the coder and compiler as to it's purpose.

In general, a good rule of thumb is don't try to outsmart the compiler unless empirical performance profiling indicates you need to. And for the majority of cases, a bool causing a few extra bytes of memory to be consumed is not going to be anywhere near to your main bottleneck.

[Reelya]

Yup, as a rule things like this only make any real difference for data structures where you have at least hundreds or thousands of the things, or for a data structure that's accessed hundreds of times a frame.

e.g. optimizing your key input function won't make any noticeable difference in your program since you usually only poll for key info once per frame. Where you want to target your optimization is especially at looping over large sets of data. If you have small data, focus on making things clean and flexible.

e.g. for a roguelike or RTS, clearly you're going to get the best memory and speed savings by really thinking about how your map is stored/accessed, and how you represent things like units and decide when to move them, as well as optimizing your path-finding, since that involves iterating over large data sets.

[EnigmaticHat]

Line of sight and level generation are also potential bottlenecks.