OOP and Speed
BlitzMax Forums/BlitzMax Beginners Area/OOP and Speed
| ||
| Hi I've been looking through an OOP tutorial on how to create a vertical shooter: http://www.shmup-dev.com/wiki/index.php?title=Tutorials:BlitzMAX:Creating_a_Vertical_Shooter In the example when an object is created, its added to a list (for example the player) and then when the code needs to access that object, a global list is read and a local object is assigned to the last object in the list. Now I understand the reasons why this is done, but because lists are used quite a lot, I wondered if if there would be a significant drop in speed compared to the non friendly OOP method of simply: player = TPlayer.Create() ...and then directly referencing 'player' for the rest of the game (as opposed to reading it from a global list when the code needs to access it). I'd appreciate any opinions on this. Thanks |
| ||
| You should assign player that way even when using the list. Using the list has a different reason: You have a exact knowledge that the reference to the object exist and how you can remove it. If you need many controlled access to objects thought, using TMap instead of TList is a good idea .. |
| ||
| Sorry to clarify - you mean I should always assign the player: player = TPlayer.Create() ? Not sure I understand your response - it sound like you think I should do the above, but as you rightly said one of the benefits of having them in a list is an exact knowledge of objects that exist and how to remove them...? |
| ||
| If you have an instance of TPlayer you always need, then yes, you should have a straight reference to it, not only having it in the list. As the player isn't just a regular object but a very specific and central one (as all the userinput normally applies to it), using a list only would be a very bad idea performance wise. Using the list for operations is a good idea if you have for example several enemies (like in a space invader game as easy to understand example), so you can calculate the behavior of all enemies in the enemylist for one after another. As you need to do this for all enemies in the list, using the list is a good idea, as it does not have an "useless operation" overhead anymore. As well you can dynamically create new enemies without thinking about new variable names etc. |
| ||
| Thats great, thanks for clearing that up. |
| ||
| using a list only would be a very bad idea performance wise. No it wouldn't. There is no way you will be able to detect even the slightest measurable difference between the two. |
| ||
| If you have 100 entries and need exactly the player entity from ships to apply the user input, then it definitely is as you first need to find it. Lists are great if you do perform stuff to the list as whole but not if you need one specific objet from the list. (Sure you could put the player at the first position, but as you have to retrieve it over and over again the code structure is cleaner using a global player reference) If you have something you exactly need one specific, you already know when start searching, then TMap is far better performance wise. |
| ||
| then it definitely is as you first need to find it. Not if it's always the last element in the list. If you have something you exactly need one specific, you already know when start searching, then TMap is far better performance wise. Well it is with regards to searching, but not to inserting and removing (or iterating). Depends on what kind of operations you're doing. Generally, even with 100 elements in the list, you're not going to see a significant difference between a 'constant' search (array or global), and a 'linear' seach (list) unless your target is a 10Mhz 386. |
| ||
| list and array are both linear searches. But from your answer, I get that you do not have the least idea of what TMap is or does. |
| ||
| This is the way I see it: An arary use constant time as it know where to look in the memory like: something[i] , it should look at the spot of 'i'. Inserting to an array is constant IF there is room in the array. Removing is also constant but does not free the memory. Then you have to make the array smaller wich is very peformance consuming. The TMap also has liniar search as you have the a key wich determines the place to look for the object. Iterations is slower at you dont have ref from object to object. Inserting and removing is slower at it has to rebuild the map. In a List you have to go through the list until you get a mach, making the search liniar. Inserting to a list is constant as you just put a ref to the last object and removing is constant efter you found the object to remove. |
| ||
| Array only has constant if you know the index. The counterpart is that Array create an overhead when you need to dynamically resize them (intelligent system do a resize to x2 or /2. TBank actually uses a similar overallocation strategy as well as it saves you very much time in average case) TMap is implemented as a binary tree, this means not O(n) but O(log n) for searching , which is not linear. List: Only insert is constant, the other have O(n) as both have the search operation involved which has O(n) as you stated. But again: My point is, that if you have 1 specific object that is used over and over again (for example the player object), its a lot of overhead to retrieve it over and over again if you have to apply user input! (I don't say, that you shall not put it into the list! Because physical stuff etc are calculated for all dynamic objects in the exactly same way so there the object needs to be in the list. But only operating on the list is what I do not think is a good idea. While retriving might be doable in constant time, its still a higher constant than using straight the reference) |
| ||
| You have to have a lot of objects on a list before searching through them rather than accessing one directly makes a difference. Even then you can can exit once the object is found. However, I agree that saving a much-used object link away for reuse is 'handy'. |
| ||
| I am using only arrays. To remember an object I just store an int of the position of the object in the array. I use loops only when I need O(n) activity to be done by the Objects. And ussaly I am creating AABB trees to have the minnimum search when I am working with coordinates. Also a good practice is to check the double distance of the objects to check witch one is nearer to the target. |
| ||
| All this discussion brings to me a question and i figured here is the place to ask it instead of creating a new thread: I personnaly dont like TLists. For my project, i have the graphic engin, which stores all the data and methods pertinent to graphics. So i have an array of images, animations, movement scripts. This way, i can setup a sprite this way: MySprite.Init(Images[imgFrog], [Animations[aniJump], Movements[movJump]) So i have a direct access by a key or ID to the elemnt i want. So right now i dynamically work with my arrays by slicing them 1 element bigger when adding and 1 element smaller when removing) My question is: Should i be using TMaps instead? Is that what they are usefull for? Is it faster than what i'm doing? Under what conditions? My thought: Since i load everything at the start of the game, i think the array is faster, but if i was to load/unload alot during gameplay, then i should switch to TMaps? Is that correct? thanks, Smurftra |
| ||
| No it would not be faster I fear. If you know the ID, then arrays are the fastest possibility solution as you have a direct access. TMap's strong point is searching a given key within a set and thats what I use it for: Save data according their name which might be used at some point. Thats for example a very good idea (at least I think so) is using it if you have objects and need a search functionality. |
| ||
| So if i was to keep loading/unloading all the time during game, tmap would increase the speed of that portion, but decrease the speed of retrieving the object. thats how i understand it. TMap is basically like a Collection or Dictionnary in Visual Basic. Thanks for the info Dreamora |
| ||
| list and array are both linear searches. I meant to say access, obviously. With the array you can have the index, so it is effectively equivalent to your 'global' except more likely to be cached. But from your answer, I get that you do not have the least idea of what TMap is or does. Funny, because that's the same impression I get. Isn't that wonderfully argumentative? Oh and by the way, TMap is an Associative Array, not a BST. My question is: Should i be using TMaps instead? Is that what they are usefull for? Is it faster than what i'm doing? No. What you're looking for is a HashMap. Under what conditions? Under conditions where you change a lot of data around frequently and it needs to be kept sorted. TMap is basically like a Collection or Dictionnary in Visual Basic. Well I don't know about VB terminology, but yes. Dictionary and Associative Array are different names for the same ADT. |
| ||
| Oh and by the way, TMap is an Associative Array, not a BST. No, it's both. |
| ||
| No, it's both. A BST can, by definition, have 'equal' elements. An associative array cannot. Neither can TMap. |
| ||
| No, that's not correct, BSTs may be designed to allow duplicate entries, but it's not a requirement. |
| ||
| Are there hashmap modules included in blitzmax? |
| ||
| No, not so far. There are other core "structures" missing as well so far so we perhaps should build up those. Is there a page dedicated to that? I don't like the modules board that much, its crowded and the search functionality is next to useless. |
| ||
| this is very context heavy - there are places were arrays are best suited to problem, and places were lists or maps are better suited..the idea that you should use one type of storage solution for all your problems is jst madness.. which system do you feel more comfortable using?, which one best fits the problem your trying to solve? does the code your working on really need to be optimised? ..good design is good design.... |
   |