#22132 - Lord Maz - Sun Jun 13, 2004 8:32 pm
Hey, I'm doing some research to determine whether STL is suitable for GBA projects or not. I've done a quick profiling test to compare the speed of a STL list and a self-made one that does the same thing, and I'll post my results for the record.. don't take the results _too_ seriously though - the test was designed to give me a general idea how much slower STL Lists are, not to give any 100% accurate comparisons. The results i show here are how much faster my specialized list is compared to the generalized STL list:
Pushing an item: 67%
Popping an item: 15%
Searching through the items: 38%
Average: 40% faster.
What i did was counting v-blanks while pushing/popping/iterating through 7500 items. I used all the optimizing tricks i know about for the loops and such.
So, now for the question.. (took some time ;) )
Anyone have any opinions based on experience using STL in a GBA project? Do you believe my results to be accurate or am I doing it all wrong?
Thanks for any constructive replies,
/Maz
#22136 - tepples - Sun Jun 13, 2004 8:40 pm
Did you test it on hardware, or in an emulator? VBA isn't very accurate about wait states. If on hardware, did you use the default 4n/2s wait state or the 3n/1s that most commercial games immediately switch to?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#22141 - Lord Maz - Sun Jun 13, 2004 9:03 pm
I've tested it only on emulator, and I use the 3n/1 waitstate. Not that I think these particular details matter much though, as both tests had the same conditions... don't you agree?
#22155 - sajiimori - Sun Jun 13, 2004 10:46 pm
Maybe you could post some of your tests. Actual STL performance depends on the implementation, but I would expect it to be fast.
#22210 - ScottLininger - Mon Jun 14, 2004 10:00 pm
What is "STL"?
-Scott
#22211 - sajiimori - Mon Jun 14, 2004 10:06 pm
Standard Template Library, part of ISO C++.
http://www.cppreference.com/cpp_stl.html
#22242 - Sweex - Tue Jun 15, 2004 4:27 pm
Nice that someone actually tries to test the speed of STL. I think it is difficult to compare STL with something you've written yourself. STL is written with certain rules (for speed) in mind. If you use the right container, the right way then I don't see why your own class would be any faster or slower than STL (obviously there will be some margin).
When writing your own, you define the rules so you can bypass STL's rules and therefore gain speed at certain areas.
I have decided to write my own container classes, based on the idea of STL. This allows me to use the concepts of STL, but take shortcuts and make additions wherever I want... (still not saying that my containers are any faster than STL. The opposite is more likely!;-)
_________________
If everything fails, read the manual: If even that fails, post on forum!
#22244 - sajiimori - Tue Jun 15, 2004 4:49 pm
| Quote: |
If you use the right container, the right way then I don't see why your own class would be any faster or slower than STL (obviously there will be some margin).
|
Yeah, I'm specifically wondering if Maz compared a singly-linked list with std::list instead of std::slist. That might result in the kinds of figures posted earlier. I guess we'll have to wait to see the tests.
#22271 - Marill - Wed Jun 16, 2004 5:17 pm
well, here's my opinion,
you're definitely free to implement your own lists and make it work the fastest you want it to work.
STL is pretty fast tough, coz there are certain behaviours in the lists that are defined. The trick is to know what list to use in the right situation for speed.
What STL can give tough is extreme flexibility. your STL lists can work on absolutely anything - int, float, double, or your own defined classes. simply because STL uses the C++ templates.
in conclusion, STL is pretty fast, although you can definitely write faster lists, but you need to spend all that extra time to code the lists and you'll probably can use that list for a limited number of data types. STL provides you with ready made lists and iterators that you can just use, pretty fast and can work on any data types you have.
#22277 - sgeos - Wed Jun 16, 2004 8:03 pm
| Marill wrote: |
| you can definitely write faster lists, but you need to spend all that extra time to code the lists and you'll probably can use that list for a limited number of data types. |
Writing a custom list for a single data type is dead simple. One could probable come up with a macro scheme that would allow one list/tree handling library to be used with any type of data.
Instead, one could use a data type like this:
| Code: |
struct node {
void *data_ptr;
struct node *next;
struct node *prev; // If you need a doubly linked list
}; |
It is not the safest, but should work with anything.
-Brendan
#22288 - Marill - Thu Jun 17, 2004 2:36 am
sgeos, sure thing :)
the illustration is not to prove anybody right or wrong, but just to show how STL can be helpful in this case.
Unless you have only 1 element in the list, the time complexity of searching through that is O(n). Also, it doesn't store what data type you're holding in the list, so you gotta handle it elsewhere, again, more code.
it is much easier and flexible to do this with the C++ templates which STL uses. but of course, you can't garuantee it'll be the fastest.
#22289 - sajiimori - Thu Jun 17, 2004 2:56 am
| Quote: |
Unless you have only 1 element in the list, the time complexity of searching through that is O(n).
|
Is that supposed to be an argument in favor of STL lists? They have O(n) search as well. In fact, even arrays have O(n) search -- you probably meant O(n) random access, which STL lists also have.
Additionally, since the big-O notation is a function on problem size, specifying "unless you have only 1 element" is redundant.
| Quote: |
Also, it doesn't store what data type you're holding in the list...
|
Neither do STL lists. Typing is handled at compile time.
#22290 - sgeos - Thu Jun 17, 2004 3:58 am
| Marill wrote: |
| the illustration is not to prove anybody right or wrong, but just to show how STL can be helpful in this case. |
To a certain extent, the goal in arguments is to discover the flaws and merits of different ways of doing things. In so doing, a party or position my be proven wrong. I think that setting out to prove someone wrong is misguided.
One could put a "struct this_type *next;" as the first member of everything that needs to be in a list. From there a pointer to the first member of the list could be passed. One could even pass an offset to use to sort the list. The sorting routine would use void pointers, of course. I'm not sure that this is entirely safe, but I suspect it would work in practice.
Does gcc change the order of members in a struct? If so when/why?
-Brendan
#22292 - Marill - Thu Jun 17, 2004 4:25 am
I am in agreement to both of you on how you could program your own list and support different data types.
My favour for STL is it's flexibility without the need for much extra coding. It handles safely and provides you with an iterator interface to access elements within the lists, without to actually program all these things. You can use it "as is" and on different data types, even the ones you define on your own.
As for speed of access, insertion, deletion, etc, it may not be the fastest as if you code your own. Therefore the trick is to know what type of STL list to use in the different situations needed in order to avoid unecessary processing overheads. Do I need a vector, or a list, or a set or a map? These kinda questions.
#22296 - sajiimori - Thu Jun 17, 2004 5:46 am
Generic sort functions are typically done by providing a comparison function as an argument. In C, the function might be of type int (*)(void*, void*), and it would cast the void*s to the appropriate type.
I think ANSI requires that structs are not rearranged, but they may be padded.
#22955 - benjamin - Thu Jul 01, 2004 8:27 pm
My philosophy on this is to use something like an STL at the outset and then based on information I get by profiling, I will then go and write custom code with the intention of obtaining better performance.
I don't see a lot of point in pre-emptively trying to outdo the performance of a widely used and proven library like STL until your profiling gives you a good reason to.
That said, it probably pays a lot to spend up front time on deciding on which algorithms will be more efficient than which specific flavor of an implemented algorithm would be efficient. In other words linked list, or array, etc.
Yet even here you can have misleading results. While a properly weighted hashtable can give you O(1) on your lookups, doing many lookups that result in reads of discontiguous areas of memory can cause cache misses, which in certain circumstances might be a worse result than doing an O(1) search.. etc.. you get the idea..
I guess the old mantra of Kernighan, "Make it run, then make it run fast", or Knuth, "Premature optimization is the root of all evil", still apply. (appologies to them if I've botched their exact qoutes)..
#22958 - poslundc - Thu Jul 01, 2004 8:33 pm
| benjamin wrote: |
| While a properly weighted hashtable can give you O(1) on your lookups, doing many lookups that result in reads of discontiguous areas of memory can cause cache misses, which in certain circumstances might be a worse result than doing an O(1) search.. etc.. you get the idea.. |
This is, of course, irrelevant on the GBA, which doesn't have a cache.
Dan.
#22963 - benjamin - Thu Jul 01, 2004 9:43 pm
| poslundc wrote: |
| benjamin wrote: | | While a properly weighted hashtable can give you O(1) on your lookups, doing many lookups that result in reads of discontiguous areas of memory can cause cache misses, which in certain circumstances might be a worse result than doing an O(1) search.. etc.. you get the idea.. |
This is, of course, irrelevant on the GBA, which doesn't have a cache.
Dan. |
Naturally.