Faster entity information
Blitz3D Forums/Blitz3D Beginners Area/Faster entity information
| ||
One way I have stored certain information about entities, such as, mass and elasticity for physical properties, is to use a Type like so:Type PhysObj Field EntityHandle Field Phys_Mass Field Phys_Elast Field Surf_Friction Field Aero_X_l Field Aero_Y_l Field Aero_Z_l End Type What I'm wondering, is, if in generlal, simplified cases where there may be a HUGE number of such entities, would it be faster to iterate through the type for the correct entity, or, perhaps, to make use of simething like EntityName() that could store the information in an encoded format, and decode the string? Of course string manipulation is comparitively slow, in the case of, first, identifying the srelaevant segments, then decoding the string into the correct value, I am curious to if anyone knows whether this method may be faster than iterating through a huge Type list, containing over, say, 500 entities? |
| ||
The common way to associate a particular type instance with an entity is to use Handle() and Object().; Store type handle as entity name. NameEntity entity,Str$(Handle(this.myType)) ; Retrieve type from handle, stored as entity name. this.myType = Object.myType(EntityName(entity)) |
| ||
Even so, iteration would still be required, even if 'behind the scenes', for both the entity "pointer list" and the Type lists. |
| ||
Not sure I follow. If you have the entity, you have the type. No iteration required. |
| ||
In B3D copde, you have this.myType = Object.myType(EntityName(entity)) However, on compilation, assuming the machine code would be commpiled similar to C structs, the cpu will still need to iterate through some register to identify the correct address, since there's no metadata compiled with the Types. |
| ||
Surely, when calling Object with the integer ID handle, it just retrieves the associated type pointer via some kind of lookup table? Maybe I'm just misunderstanding what you mean. |
| ||
Yeah i'm sure just retrieves the pointer. Besides, it's fastest way to jump straight to a type object in blitz. I certainly would think parsing a string for this field data would be a good bit slower. |
| ||
it just retrieves the associated type pointer via some kind of lookup table? Computers CANNOT just look up numbers. Any interaction with tabular information requires starting at the beginning and going through each entry until it reaches the required one. Besides, it's fastest way to jump straight to a type object in blitz. That's my point, might it be faster to just use the entity and its name, rather than a Type structure? |
| ||
Computers CANNOT just look up numbers. Erm, yes they can. Its called a pointer. To answer the original question: I definitely wouldn't parse a string. If fast searching is needed, you may want to keep references to your types in a dictionary/tree structure of some sort. |
| ||
Computers CANNOT just look up numbers. What? You think, for example, accessing a specific array element requires iterating through the entire array until the correct element is reached?Any interaction with tabular information requires starting at the beginning and going through each entry until it reaches the required one. It's simply a matter of pointer arithmetic. |
| ||
CANNOT ugh.. |
| ||
Thanks, all tsorry for the misunderstanding. Yeah I see how it works with Handle() now :) |
| ||
See also hashing and search trees. Iterating through a list is not only not the only way to access data, it's very often a pretty poor way to do it. |
| ||
[quopte] Iterating through a list is not only not the only way to access data, it's very often a pretty poor way to do it. [/quote] Yeah, that was my main reason for posting. Though I hadn't correctly understood how pointers work, which certainly speed things up there. As for hashing at least, that's something I have seen and heard a lot about but definitely need to read up on |
| ||
Right, well kinda following on from the above, how "bad" is it to keep switching between, Type objects and handles, or is there really no real difference? For example, say I have functions that work in this way: Function GetInformationA(Instance.MyType) Return Instance\A_Field End Function Is it significantly 'worse' to use: Function GetInformationA(MyHandle) Local Instance.MyType=Object.MyType(MyHandle) Return Instance\A_Field End Function In theory it should be basically the same, right? |
| ||
Everytime you create a handle, you actually increment a counter in blitz. In theory, you could be storing references to objects, that could get over written if you generate enough handles to roll over the maximum value of an integer. With regards to your question, i really doubt the actual speed difference matters. |
| ||
Thanks Ross, memory is important as well as speed, so the counter thing is intriguing. Sure, it's probably unlikely that other memory would be overwritten unless a ridiculous number of separate handles were used. Would this counter still increment even if you are re-using the same handle? Say, for example, Function One(blah) Local ReUseHandle=LoadWhatever(blah) End Funciton Function Two(bling) Local ReUseHandle=LoadWhatever(bling) End Function [/code] Now imagine calling either or both One() and Two() multiple times, not sure how many, but a lot, perhaps if every time some data needs to be looked at or worked with... Again, I'm guessing it should be safe enough, since the handle will always return the same value, and naturally would be overwriting itself? |
| ||
The speed difference is about one order of magnitude, so it's negligible if your list is only a few hundred items long, or you're not checking every item every loop. Wouldn't worry about this for 3D entities as the number of 3D objects will slow down your scene long before the Object/Handle operations will! Handle() provides a unique integer for every type object (of all types). If LoadWhatever returns the same object, it will have the same handle; if it doesn't, it won't. So you re-use handles by re-using type objects; otherwise there's no way to control it. Has anyone actually tested what happens when you overflow the counter? I wasn't patient enough to wait for my test to allocate and deallocate objects four billion times (my programs have so far operated on the assumption that this wouldn't occur). I live in hope that Mark did something really clever (once again) and that the Handles will seek out "dead" slots past a certain point... |
| ||
the number of 3D objects will slow down your scene long before the Object/Handle operations will! That's a good point :) Thanks Yasha. I am curretnly just dealing with a few hundred instances, and all my functions are referring to Handles as far as return values and parameters, with the guts of the functions performing any necessary Object.MyType(MyHandle%) 'conversions'. Has anyone actually tested what happens when you overflow the counter? I wasn't patient enough to wait for my test to allocate and deallocate objects four billion times (my programs have so far operated on the assumption that this wouldn't occur). I live in hope that Mark did something really clever (once again) and that the Handles will seek out "dead" slots past a certain point... Presumably, this could also occur with ANY handles (i.e. those from LoadImage or LoadSound etc. too) Any instance where there's more than 4 billion or so individual 'objects'. Maybe there's some form of internal 'checking' that can differentiate the 'class' of an object, such as whether it's a Sound or an Image which could then hopefully mean that a duplicate handle 'value' could be usedprovided the objects are a different class? i.e. a=LoadImage("pic.bmp") b=LoadSound("sound.wav") where (a = b) Who knows? In all likelihood, any program that DOES have that many currently "active" handles could benefit from some optimisation, so I think it's extremely unlikely to be an issue |
| ||
This has been tested before. I ran some tests, as did someone on an IRC channel. The counter overflows goes from (just making up numbers to illustrate the point) 0 to 2336373829 to - 2336373828 back to 0. Upon reaching 0 it will overwrite the existing counters. There is no seeking out dead slots. It would be wise to keep track of this yourself, if you intend to use generate and discard lots and lots of handles. |
| ||
Thanks Ross that's handy to know! |