Elysian Shadows

What is this 0(1) notation you're using?

:S

It's just some notation to describe (algorithmic) complexity. O(n) means an algorithm that has some sort of input of size n runs in linear time (e.g. finding the maximum in an array of n ints). O(1) means constant time, so regardless the input size it takes a constant amount of time/steps to run. wikipedia/google Big-O Notation if you are into math

Often it makes little sense to tune O(1) code but I guess in games when it's part of the main loop that needs to run as fast as possible you should think about it after you are done optimizing the more critical parts (like collision detection etc.) but honestly I wouldn't give it much thought. Rather stick to good OO design and worry about tuning something like that once the game works.

fantastico wrote:It's just some notation to describe (algorithmic) complexity. O(n) means an algorithm that has some sort of input of size n runs in linear time (e.g. finding the maximum in an array of n ints). O(1) means constant time, so regardless the input size it takes a constant amount of time/steps to run. wikipedia/google Big-O Notation if you are into math :)

Right. It means that the runtime in the worst case is determined by nothing [which would be constant time], or some function of the number of elements "n". Generally constants are left out. For instance, if the runtime is 2n well the 2 never changes, so it's just O(n). Other common runtime things are
O(1) - constant time
O(log(n)) - logarithmic time (every lookup halves remaining lookups you have to do until you find your goal; binary tree algorithms run in this time)
O(n) - linear time (you always have to go through the whole list)
O(nlogn) - no real name for this one
O(n^2) - polynomial time (this is the most common 'bad'. after you find your first result, you have to do another n lookups)
O(n^c) - polynomial time (c is an integer)
O(2^n) - exponential time (this is very bad)
O(n!) - factorial time (this is horrible)

http://en.wikipedia.org/wiki/Big_O_nota ... _functions

Back to vtables, does the vtable lookup involve iterating through the table? If so then it's O(n).

MarauderIIC wrote:Back to vtables, does the vtable lookup involve iterating through the table? If so then it's O(n).

The wikipedia article says no. Since the compiler knows about all virtual functions at compile time it can also come up with a static "name to table-index" mapping that won't change at runtime so whenever it sees a virtual function call it substitutes it with a call to the function pointed to by the table at the known index.

Don't know. I suggested O(1) because they could resemble a hash table internally. Otherwise, it would be a linear traversal at worst (O(n)), unless C++ is internally overcomplicated and randomly does a double take here and there.

Meaning, at worse access of the table would be ~equal to the number of levels of inheritance you have (each additional virtual definition with the same signature as the method is added to the table as a function pointer). And, though vtables may seem a bit gay at times, they're quite nifty when polymorphing objects. ;p

Wow, we completely butchered this topic.

edit: Aw, didn't see your post as I typed this. So yeah, it's O(1) (hashtable). That's not a speed to be bitching about.

VTables are two fetches.

The parent function (to be inherited by everything) has a this_object() pointer pointing to the vtable containing all methods for each object. If you create the object as a parent, its constructor makes the this_object() point to the parent vtable. If you construct it as a child, the child's constructor forces this_object() to point to the child's vtable.

You're adding an extra two fetches. One to follow your this_object() pointer and one to point to the correct function. As for memory overhead, each class in the hierarchy must have its own vtable.