MemCopy() faster than slice.
BlitzMax Forums/BlitzMax Programming/MemCopy() faster than slice.
| ||
| Early tests have shown memcopy() to be faster than slice when downsizing an array. In the test code I create an array large enough to hold the max # of elements of a list. Then I loop through the list and add objects that meet a pre-defined condition (in this case it's a hash table and only objects with the given entry name are inserted into the array). Given that there may be empty elements at the end of the array (if one or more of the condition tests failed), I keep track of the actual insertions into the array and then downsize the array to that number. These are the two approaches I tested to handle resizing the array. 'approach 1 MemCopy( retarray, retarray, SizeOf(retarray[0]) * objectcount) 'approach 2 retarray = retarray[..objectcount] retarray is an array of objects. It is initialized to a size >= objectcount. objectcount tracks the # of actual, filled elements in the array. In my code there's no way to know beforehand how many elements will actually get filled. So the array might be initialized as "new object[500]", but then only get filled with 300 entries. The test shows that the MemCopy() approach is indeed faster. Not significantly faster, mind you. I'm getting approx 100-200 ms difference per 10,000 iterations of the above code. As I mentioned, this example was tested with a hash table, and in my MUD server code I'll be accessing hash tables often enough that, despite the speed difference being small, it'll make a difference in the long run. Just thought you might like to know. (if anyone wants some code to run/test I can supply it.) |
| ||
| Surely MemCopy is faster because it misses one of the most elemental points in BM: Slice tells the GC which objects are not needed anymore if there are any in the sliced area. MemCopy does not comunicate with the GC it is for unmanaged (the alloc commands or CStrings / WStrings) operations on memory blocks only. So what you create in the end is a memory leak if you didn't clean the array before sizing it down. |
| ||
| Hmm, good point. :) Okay, so I guess the fact that MemCopy is faster is relatively moot except for rare cases where you're downsizing an array and only removing elements that you *know* are empty. Lucky for me, that's exactly what I'm doing. ;) It's actually (potentially, depending on my hash table size) a lot faster than looping through the table to get the correct # of elements and initiating the array to the 'correct' size. I kill an unnecessary loop and replace it with a fast MemCopy. |
| ||
| MemCopy( retarray, retarray, SizeOf(retarray[0]) * objectcount) If you copy from retarray to retarray, it will do nothing;-) |
| ||
| Well, all I was using it for really was to update the internal "length" field of the array. Come to think of it though, my tests weren't actually testing to see if it worked since the only time the array would be a smaller size than it's initialization size was during a hash collision with different names (multiple hash entries of the same name are no problem). Come to think of it, I doubt that the length field is being updated anyways. Hmm, I'll have to tweak things a bit. [edit] It'd be nice if I could just tweak the length parameter myself, although I understand why that's not possible ;). Maybe I'll just make a wrapper class that stores the length. |
| ||
| If your only problem is the length, it isn't a problem. Just keep a variable aside with your hash array and use that instead of the arrays length :) Or a HashTable class, which holds the array and the length used currently ^^ |
| ||
| Well, I can't really do that because what I'm doing is...well, in this particular hash table class I'm allowing multiple entries with the same name. So there might be 20 different calls to hash like so Hash( "reusable key", rand(20 )) The problem is in my lookup function that returns multiple entries for a given hash key. It returns all entries that have the name specified, so ReturnEntries( "reusable key" ) returns an array of objects that match that key. I can't simply assume that every entry in the same bucket that "reusable key" gets put in though, actually has a hash key of "reusable key." If there was a hash collision, some other entry or entries may be residing in the same bucket. So in my ReturnEntries( key:string) function I create an array of objects = to the # of items in the bucket, and then loop through an insert every entry that matches the key parameter. If there were any hash collisions though, the # of objects that gets inserted into the return array is going to be less than the actual array, hence my need to downsize the array. I've been doing some more speed tests and the wrapper method is the fastest when there are few collisions and relatively few duplicate key entries per bucket. The slice method is almost as fast and is actually faster when there are a lot of duplicate key entries. The third method I've tested is to scan the list of entries for a given key, keep track of the count and then initialize the array to the proper size, and then re-scan the list and insert all the matching entries. The double "for each-in" loop though makes this the slowest method by far. |
   |