Hard Light Productions Forums
Off-Topic Discussion => Programming => Topic started by: Uchuujinsan on November 22, 2009, 04:53:38 pm
-
Very interesting video about the internal workings and optimizations of the hardware and the compiler, and how it does affect programming in c++/c#/java
http://www.nwcpp.org/Meetings/2007/09.html
Direct link to video:
http://video.google.com/videoplay?docid=-4714369049736584770#
Direct link to the slides:
http://www.nwcpp.org/Downloads/2007/Machine_Architecture_-_NWCPP.pdf
-
very interesting.
never ever ever use anything other than a vector.
-
very interesting.
never ever ever use anything other than a vector.
whoa there. There are damn good reasons for the existence of other structures.
Just try an algorithm that requires a heck of a lot of non-head or tail insertions.
-
I was being overly simplistic.
-
*phew*
-
but that does reinforce my existing bias flavouring vectors as a first choice.
-
This confirms my instinct of "it's not fast until you test it."
However I want to point out that lists are often significantly faster then vectors for completely different reasons (as well as having O(1) time for insertion and deletion).
-
Lists have an issue with data locality (so they're not brilliant for caching - avoid in tight, inner loops unless you want to miss the cache a fair bit)
They also have the issue of you can't just access element 10, you need to follow the list until you get to element 10.
Insertion/deletion time is good though :)
-
Well yeah, but what's so special about element 10?
That is, while a list can't do the whole random access thing, you don't necessarily need random access anyway. So it may not matter.
-
There's also the fact that most of the time, optimizing the way your data is cached to get a speed increase isn't usually super-high priority.
But it is nice to know about cache locality issues so when you *do* for some reason need to be really clever, you can.
-
Lists have an issue with data locality (so they're not brilliant for caching - avoid in tight, inner loops unless you want to miss the cache a fair bit)
They also have the issue of you can't just access element 10, you need to follow the list until you get to element 10.
Insertion/deletion time is good though :)
Actually if you're trying to access list element 10 then you should probably be using a vector. In all of my lists, I only ever need to access all of the elements in order, or the element I need to access has a pointer in some other object.
-
Lists have an issue with data locality (so they're not brilliant for caching - avoid in tight, inner loops unless you want to miss the cache a fair bit)
They also have the issue of you can't just access element 10, you need to follow the list until you get to element 10.
Insertion/deletion time is good though :)
Actually if you're trying to access list element 10 then you should probably be using a vector. In all of my lists, I only ever need to access all of the elements in order, or the element I need to access has a pointer in some other object.
I believe that was implied by what he said.