Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

EA open sources their internal version of STL

github.com

Post reply on HN
Print view View original

11–20 of 37 posts

Re: EA open sources their internal version of STL

#11

Post by terryjsmith »

archangel_one wrote: post #6
terryjsmith wrote: post #5

Earlier quoted context omitted.

I imagine most STL classes still don't fit game programming paradigms. My very first experience with this was using vectors to store vertices as an intermediary before sticking them into a vertex buffer. Granted, my math was awful, but the memory overhead was absurd. I constantly find myself over using STL in my programs because of how easy it is, then redoing it to use standard C/C++ arrays, linked lists, etc. for e…

Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?

Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage.

I think STL is a great set of libraries, but I also think they're sometimes too easy to use if you don't consider alternative implementations and the impact of each way.

Re: EA open sources their internal version of STL

#12

Post by albertzeyer »

NickPollard wrote: post #10
archangel_one wrote: post #6

Earlier quoted context omitted.

Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?

You're being more tolerant. When you're building a high performance game engine for fixed target hardware, the last thing you want is to be doubling up the size of your arrays.

If you know before the allocation how much entries it must hold at maximum, you can give an std::vector that information. There is simply no case where you are forced to require more memory with an std::vector but not with a manual implementation.

Re: EA open sources their internal version of STL

#13

Post by georgecmu »

terryjsmith wrote: post #11
archangel_one wrote: post #6

Earlier quoted context omitted.

Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?

Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage. I think STL is a great set of libraries, but I also think they're sometimes too easy to use if you don't consider alternati…

For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat.

That doesn't sound right at all. Of course, if you add or remove objects at the vector's head, all of its data will be moved, though probably not reallocated. But if you have a need for frequent additions and deletions anywhere but the tail of the vector, you picked a wrong data structure. Double ended queue () would would've suited you much better.

Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage.

Did you reimplement element addition/deletion logic from scratch?

Re: EA open sources their internal version of STL

#14

Post by jemfinch »

terryjsmith wrote: post #11
archangel_one wrote: post #6

Earlier quoted context omitted.

Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?

Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage. I think STL is a great set of libraries, but I also think they're sometimes too easy to use if you don't consider alternati…

> Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat.

If that was the case, you were doing something wrong.

Re: EA open sources their internal version of STL

#15

Post by georgecmu »

terryjsmith wrote: post #5
jrockway wrote: post #4

This is why game companies use C++. They've already reimplemented it internally and don't ever want to do that again.

I imagine most STL classes still don't fit game programming paradigms. My very first experience with this was using vectors to store vertices as an intermediary before sticking them into a vertex buffer. Granted, my math was awful, but the memory overhead was absurd. I constantly find myself over using STL in my programs because of how easy it is, then redoing it to use standard C/C++ arrays, linked lists, etc. for e…

If you implemented this as follows, then yeah, you'll get log(N) reallocations, where N is your final vector size. But if you have a pretty good idea of what N is, you should set capacity at the time of vector declaration to avoid useless reallocations. You shouldn't expect any library to make this sort of predictions for you.

vector vec;

while(getData(v)) { vec.push_back(v); }

Re: EA open sources their internal version of STL

#16

Post by archangel_one »

NickPollard wrote: post #10
archangel_one wrote: post #6

Earlier quoted context omitted.

Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?

You're being more tolerant. When you're building a high performance game engine for fixed target hardware, the last thing you want is to be doubling up the size of your arrays.

If you don't overallocate the vector then push_back() runs in linear time instead of amortized constant which is generally a worse tradeoff. You can avoid the whole issue by calling reserve() ahead of time, but if you don't know how many elements you're going to have then you're in trouble, but you won't be able to do much better by replacing vector with your own array either.

Re: EA open sources their internal version of STL

#17

Post by archangel_one »

georgecmu wrote: post #13
terryjsmith wrote: post #11

Earlier quoted context omitted.

Sorry, you are correct; I should have been more specific: the memory management overhead was tremendous. For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. Moving to a fixed size array in C++ I saw an easy 50% drop in CPU usage. I think STL is a great set of libraries, but I also think they're sometimes too easy to use if you don't consider alternati…

For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. That doesn't sound right at all. Of course, if you add or remove objects at the vector's head, all of its data will be moved, though probably not reallocated. But if you have a need for frequent additions and deletions anywhere but the tail of the vector, you picked a wrong data structure. Double end…

I wouldn't call myself an expert on vertex buffers, but IIRC the OpenGL API to load data into a buffer just takes a pointer to the data and a size, so requires that your data is contiguous in memory beforehand - so deque may not have been an option.

Re: EA open sources their internal version of STL

#18

Post by rbancroft »

NickPollard wrote: post #10
archangel_one wrote: post #6

Earlier quoted context omitted.

Any sane implementation of std::vector is probably going to have three pointers of overhead, and might allocate twice as much memory as required in the worst case when you push a bunch of objects into it. That doesn't seem totally absurd to me - was yours much worse, or am I just being more tolerant of it?

You're being more tolerant. When you're building a high performance game engine for fixed target hardware, the last thing you want is to be doubling up the size of your arrays.

So are you claiming there is a better way to grow a vector? Or are you mistakenly criticizing vector for a task it isn't suited for.

Re: EA open sources their internal version of STL

#19

Post by georgecmu »

archangel_one wrote: post #17
georgecmu wrote: post #13

Earlier quoted context omitted.

For every object added and removed, the vector and all of it's data was basically reallocated, moved, deleted, repeat. That doesn't sound right at all. Of course, if you add or remove objects at the vector's head, all of its data will be moved, though probably not reallocated. But if you have a need for frequent additions and deletions anywhere but the tail of the vector, you picked a wrong data structure. Double end…

I wouldn't call myself an expert on vertex buffers, but IIRC the OpenGL API to load data into a buffer just takes a pointer to the data and a size, so requires that your data is contiguous in memory beforehand - so deque may not have been an option.

Agreed. But I can't think of any data structure that would offer you contiguous, order-preserving storage and O(1) insertions/deletions of arbitrary elements.

Re: EA open sources their internal version of STL

#20

Post by aaronblohowiak »

jrockway wrote: post #9
ig1 wrote: post #8

Earlier quoted context omitted.

A surprisingly large number of companies have their own STL implementations from Investment Banks to Telecoms companies. Often because they're doing funky things (often related to memory allocation) which would be outright impossible to do in languages like Java or C#.

I have never seen anyone mix their custom memory manager with STL. Also, who said anything about Java or C#?

Right, they have a custom STL because they want to have their custom memory management.
Post reply on HN