Hey there!
I've got a question which's not really related to Assembly (which's why I'm posting it here), but first a little background to why I'm asking it.
I'm developing a project in C at the moment (with some routines written in Assembly), and I'm currently in a position where I've got to choose what type of data structure to use with regard to performance and speed, but I'm unsure what to choose. I'll only insert elements once (ie. when parsing a file), I'll never be removing any elements, and I'll never access the data randomly (it'll be sequentially). So what I'll be doing is - iterate through the data structure (which could be big) from start (0) to end (count) to find an element, and I'll be doing this operation many, many times over and over again (with a different element to find each time, of course).
So, all I'll be doing is essentially this (psuedo-code):
for each element in elements
check if other_element matches element
if so do_something
end check
next element
"Element" here is a pointer to a structure.
What data structure should I use to gain as much performance as possible? Would a simple dynamically allocated array be enough here? Or perhaps a linked list?
Thanks a lot! :bg
Regards,
Seb
This all depends upon what you are actually searching for.
1. You will search for something within the data pointed to by an element in the array of elements (pointers).
2. You have a pointer into the data, and you want to know which element this is, i.e. the record number.
3. Something else we can't guess.
Each choice will bring up other questions. Perhaps a concrete example of the data (fake data is fine), would help get an answer.
Jimg,
thanks for the reply. I'd say the first point is what I'll be doing.
More psuedo-code:
for each element in elements
if element->value=other_element then
call do_something
end if
next element
"Value" and "other_element" in this case are DWORDs. So I'll be comparing DWORDs throughout the iteration, but this design might change in the future (I might switch to a byte array which'll mean I'll be doing memcmp()'s instead).
So yes, I'll be searching an array of elements (pointers to structures) for a DWORD value. The structure itself in which the value might be is quite small (< 50 bytes), and all structures will have been allocated and stored in memory after the parsing of the file is done. This actually draws me to another question I've got: what memory allocation method is preferred for many small (< 50 bytes) and quick allocations? Global/Local/Heap/VirtualAlloc?
Thanks again. :U
Regards,
Seb
To answer your last question first, I would normally make my best guess as to how much memory I will need, perhaps based upon the size of the file or other crieria, then use HeapAlloc with the next larger 16K amount. If I find that wasn't enough, I would then use HeapReAlloc to add another 16K as needed. You will find that everyone has their preferred method of allocating memory, so hopefully someone else will respond also.
As for the other part, I'm just not getting it. If you are storing the data sequentially, then the pointer you are storing will also be in increasing order, so I would do a binary search. But since you already know the value, what's the point of searching? You already have the pointer to the data. So obviously, I don't understand what you are saying yet.
Jimg,
thanks for the tip regarding the memory allocation.
As for my first question, I'm not searching for a specific value (as I perhaps did write or make you think), but I want to identify the structure holding the ID I'm using to search because I need the other information stored in that structure.
for each element in elements
if element->value=my_value then
do something with element
end if
next element
"my_value" is not an ID or index, so that's why I've got an "if" in there to compare the specific values. And the psuedo-code above is assuming "elements" is an array.
So if I've got an array/linked list/whatever which holds all pointers to the structures, and eg. I want to check if there's a pointer to a structure in there with the "value" member set to 0x10000000, and such an entry exists, I want the loop/iteration/whatever to find that entry and return me a pointer to the structure or do something with the information inside the structure.
So my question from the start was, what data structure would be the fastest and most efficient to use for this kind of operation, also taking the other facts into consideration (eg. that I'll never modify/remove entries in the data structure after the data structure has been built up, etc.)? It may sound complicated, but it's really not.
Thanks! :bg
Regards,
Seb
Ok, for an example, assume you have the following:
array of
pointers
to data
(structures)
(note: assume all addresses in decimal for this example)
address actual
within pointer
pointer value
array
10000 20000
10004 20050
10008 20100
10012 20150
Data
20000 Id (4 bytes)
20004 Name (20 bytes)
20024 Quantity (4 bytes)
20028 Spares (22 bytes)
20050 Id (4 bytes)
20054 Name
etc.
20100 Id
etc.
.
.
.
As I understand it, you want to find the structure (record) that contains an Id of 12345
Do you want the address within the pointer array, or the actual address of the data itself?
Will the data record (which you call a structure) be a fixed size or a variable size? I.e. will all records be 50 bytes, or will some be larger, some smaller?
Can the addresses within the pointer array change?
If not, are they assigned sequentially?
I'll probably have more questions after I understand these.
Hi Jimg,
yep, you got it right. Using your example, I'd want to find a structure (or data record) with the ID of eg. 12345, but this ID will not be constant as I'm fetching new IDs and do the same thing, ie. check if they're in the array/linked list/whatever I end up using.
I want the address of the data itself, that is, I want a pointer to the structure with the "ID" itself, so I easily can process the rest of the information in the structure.
The structure will be fixed-size, and the structure type itself will be byte-aligned as I'm parsing a binary file and then mapping the file data into multiple sequential structures. By the way, will there be performance penalties because of the byte-alignment of the structure when accessing individual member fields in a structure from the pointer array? If so, would copying the data to a new structure of 4/8/16-byte alignment and then freeing the old structure perhaps speed things up when iterating through the pointer array and accessing the pointers? I'm not very concerned with the performance when parsing the file, the most important thing is that I've got an efficient method of storing the structures, and accessing them from beginning to start (or the other way round) many, many times in a row.
I guess the addresses within the pointer array could change, but if they do, it wouldn't be by me - all I'll be doing is accessing all the structure pointers over and over again, and this has to be fast and efficient.
I don't know yet if they'll be assigned sequentially, I guess that depends on what data structure (ie. linear array, linked list, etc.) I'll end up using and how/where the memory allocator stores the data, or? Or did I misunderstand you?
Regards,
Seb
To answer what questions I can, yes, there is almost always a penalty for accessing data that is not dword aligned.
For the best performance, I would create my structure to be a multiple of 4 bytes. If I could afford the memory, I would align each interior element on a 4 byte boundary, assuming you might want to search on other elements rather than just ID.
This can waste a lot of memory if you have fill, but results in the quickest access.
Now, since the data is stored in a fixed size structure, and the array of pointers itself doesn't seem to contain anything other than the start of each data block, and the data doesn't seem to be in any particular order, I would not use the array of pointer at all, but just step through the data itself (only if you can align the start of each structure on a dword boundary).
I would do something like this-
mov esi,startofdata ; startofdata is the pointer that heapalloc returns to you.
mov eax,valuetofind
.repeat
.if eax==[esi]
mov eax,esi
jmp done
.endif
add esi,sizeof structure
.until esi> endofdata ; last addresses used when storing data.
mov eax,-1 ; meaning id not found
ret
Perhaps I'm missing something here, but if there will be very many elements the binary versus sequential search decision will have a bigger impact on performance than the alignment of the data. If the data will be copied to memory anyway, perhaps it could be inserted in a binary tree (or trees if there will be more than one search field) and in the process manipulated to align the search field(s).
Hi Michael-
I agree. My ineloquence is causing trouble dragging the info needed out of Seb. This would definitely be the next step if the performance warranted the added complexity.
:toothy It's actually not too hard. A linked list of structures of arrays.
Your unoptimized one:
ILKO struct
var1 dd ?
var2 dd ?
var3 dd ?
ILKO ends
Your optimized:
CLUSTER_SIZE equ 1024
ILKO_CLUSTER struct
;----[ linked-list stuff ]--------[
pPrev dd ? ; ptr to previous ILKO_CLUSTER in the linked-list. Optional
pNext dd ? ; ptr to next ILKO_CLUSTER in the linked-list
;---------------------------------/
;-----[ allocated bitfields stuff ]---------[
NumAlloc dd ? ; 0..CLUSTER_SIZE
AllocBitfield dd (CLUSTER_SIZE/32) dup (?)
;-------------------------------------------/
_padding db 20 dup (?)
;----[ structure of arrays ]-----------[
var1_a dd CLUSTER_SIZE dup (?)
var2_a dd CLUSTER_SIZE dup (?)
var3_a dd CLUSTER_SIZE dup (?)
;--------------------------------------/
ILKO_CLUSTER ends
;------[ assemble-time watchdog macro ]----------[
CheckStructMemberAlignment macro structMember
local intX
intX = structMember and 31
if intX ne 0
.err <please set _padding appropriately to align to 32-byte cache boundaries>
endif
endm
;-----------------------------------------------/
; do check on our struct
CheckStructMemberAlignment ILKO_CLUSTER.var1_a
In addition, in each "cluster" (yea, my terminology here was bad) you can put indexing info, hashing (easy), min/max values-info (easiest). And as you can see, saving/loading to/from a file is a breeze. By adding an IsDirty flag to "clusters", you can also minimize HDD activity (though you need to align to 64kB size of saved struct).
And also you can have a "NextFreeElementIndex dd ?", when appending new data (when NumAlloc<CLUSTER_SIZE), as you will mostly (or only) be appending new elements and will rarely (or never) be deleting elements.
Hash tables are definitely the fastest data structures, since they almost always take O(1) time to insert/access any element. However, they can incur slowdowns (as well as wastage of space) if their hashing algorithm does not distribute the elements uniformly enough.
If you can settle for O(log n) time, then I would recommend a height-balanced tree such as an AVL tree. It is relatively "worry free".
Here's a way to not-waste space via hashtables:
(for simplicity, 4 hash values are possible: )
int IndexOfHashElements[5]; // IndexOfHashElements[4] serves as a count of all elements
void* AllHashElements[1000];
void AddElement(int ElementHash,void* pElement){ // ElementHash=0..3
if(IndexOfHashElements[4]>=1000){ // debugging
debugCRASH("AllHashElements[] is already full here");
return;
}
//-----[ make space for the new element ]----------[
// i.e the AllHashElements[] is "aaabbcddd0" and we're inserting a value with hash "b"
// 0 = empty space, a/b/c/d are elements with those 4 hashes,
// B is the new element, we're about to insert
// so, we make the arrays like this:
// pass 1: aaabbc0ddd // we move the first "d" element to the first untaken cell
// pass 2: aaabb0cddd // we move the first "c" element to the emptied cell from pass1
// pass 3: aaabbBcddd // we put the new element in the emptied cell from pass2
for(int curhash=3;curhash>ElementHash;curhash--){ // these are those pass1, pass2, pass3 ...
int arraystart;
int arrayafterend;
arraystart = IndexOfHashElements[curhash];
arrayafterend = IndexOfHashElements[curhash+1];
AllHashElements[arrayafterend] = AllHashElements[arraystart];
}
//-------------------------------------------------/
// insert current element
int elemIndex = IndexOfHashElements[ElementHash+1];
AllHashElements[elemIndex] = pElement;
//----[ increment indices ]-----------------------[
for(int curhash=3;curhash>ElementHash;curhash--){
IndexOfHashElements[curhash]++;
}
//------------------------------------------------/
}
And encapsulate this into a linked-list structure. The above code makes uneven hashing waste less space. I.e 1000 dwords max here instead of NumHashes*1000 dwords max with linked-lists of arrays.
You just have to KNOW almost exactly how fast some operations are, how much RAM you can waste, what could go wrong, and what exactly you want the data to be. That way you can create the fastest solution to any problem.
All this really depends upon how many items there are, and how many times Seb needs to look up a value. A one time sort of the addresses of a million items would take under a second, and then a binary search each time would probably be very quick and much simpler and quicker to initially set up than a linked list.
Quote from: Jimg on March 03, 2008, 04:27:24 PM
All this really depends upon how many items there are, and how many times Seb needs to look up a value. A one time sort of the addresses of a million items would take under a second, and then a binary search each time would probably be very quick and much simpler and quicker to initially set up than a linked list.
Yeah, I forgot to add to the list of things one has to know before starting to design, :red... the most important thing - the user-input data info XD. Namely: how much data, how often, what types, what operations, how many users in parallel.. take whatever info on what the design/app needs to handle.
I would second the comment to use a hash table in this context as I have one I use regularly for data structures like this. The trick is to use a hash design that has a decent distribution across the has table range and very fast collission handling. The general test for a hash design is at what percentage of the hash table it starts to slow down and the good ones start to slow down when about 80% full which is not a problem as they are usually used up to about 50%.
Here is a PB assembler function that hashes a word against a reversed table of prime numbers.
' «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
FUNCTION szhash_word(ByVal wrd1 as ASCIIZ PTR,ByVal cnt as DWORD) as DWORD
#REGISTER NONE
! jmp nxt
' ******************************
' reverse table of prime numbers
' ******************************
phtbl:
! dd 2939,2927,2917,2909,2903,2897,2887,2879,2861,2857,2851,2843,2837,2833,2819,2803
! dd 2801,2797,2791,2789,2777,2767,2753,2749,2741,2731,2729,2719,2713,2711,2707,2699
! dd 2693,2689,2687,2683,2677,2671,2663,2659,2657,2647,2633,2621,2617,2609,2593,2591
! dd 2579,2557,2551,2549,2543,2539,2531,2521,2503,2477,2473,2467,2459,2447,2441,2437
! dd 2423,2417,2411,2399,2393,2389,2383,2381,2377,2371,2357,2351,2347,2341,2339,2333
! dd 2311,2309,2297,2293,2287,2281,2273,2269,2267,2251,2243,2239,2237,2221,2213,2207
! dd 2203,2179,2161,2153,2143,2141,2137,2131,2129,2113,2111,2099,2089,2087,2083,2081
! dd 2069,2063,2053,2039,2029,2027,2017,2011,2003,1999,1997,1993,1987,1979,1973,1951
! dd 1949,1933,1931,1913,1907,1901,1889,1879,1877,1873,1871,1867,1861,1847,1831,1823
! dd 1811,1801,1789,1787,1783,1777,1759,1753,1747,1741,1733,1723,1721,1709,1699,1697
! dd 1693,1669,1667,1663,1657,1637,1627,1621,1619,1613,1609,1607,1601,1597,1583,1579
! dd 1571,1567,1559,1553,1549,1543,1531,1523,1511,1499,1493,1489,1487,1483,1481,1471
! dd 1459,1453,1451,1447,1439,1433,1429,1427,1423,1409,1399,1381,1373,1367,1361,1327
! dd 1321,1319,1307,1303,1301,1297,1291,1289,1283,1279,1277,1259,1249,1237,1231,1229
! dd 1223,1217,1213,1201,1193,1187,1181,1171,1163,1153,1151,1129,1123,1117,1109,1103
! dd 1097,1093,1091,1087,1069,1063,1061,1051,1049,1039,1033,1031,1021,1019,1013,1009
nxt:
! xor ecx, ecx
! xor edi, edi
! mov esi, wrd1
! jmp inlp
stlp:
! add edi, 1
! add esi, 1
! mov ebx, phtbl[edi*4] ; extract prime based on character position
! mul ebx ; mul character by location
! add ecx, eax ; add result to total
inlp:
! movzx eax, BYTE PTR [esi] ; zero extend character
! test eax, eax
! jnz stlp
lpout:
! mov eax, ecx ; multiply the total by itself
! mul ecx
! mul cnt ; mul EAX by cnt
! mov FUNCTION, edx ; return remainder
End FUNCTION
' «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
Thanks for all the replies, guys, it's been interesting to read! After doing some thinking and comparison of algorithms on my own, I ended up identifying hash tables as the most efficient and suitable method for suiting my needs.
Am I right in thinking that hash tables are efficient and fast, and suit my needs perfectly with this issue? If so, I'm not entirely sure how to use hash tables with structure [pointers], or if it's even possible at all. I need to look into that if I do use hash tables.
Regards,
Seb
Hmm. Lets recap the situation.
Ok, you have a single collection of items where each item has a unique 'value' field. You will never delete items from this collection, but you will be adding and altering items dynamically, but will never alter the value field of an existing item.
You intend to perform many queries. These queries entail asking "Does an item with this value exist?" and "If true then where is it?"
If the above recap is so far true, then can you detail how often (overall) these queries will fail?
This is important in deciding what data structure is probably "best".
A high rate of "does it exist?" failures means that that initial query efficiency is significantly more important than anything else. In extreme cases the "where is it?" could be very very slow (such as reading them off disk, or rescanning an entire file!) without any noticable impact in performance.
Also, can you detail the limits of the 'value' field? Are they strings? 32-bit integers? If they are 32-bit integers then consider that 4 gigabits is "only" 512 megabytes, such that a single bit test instruction could infact perform your initial query of "does it exist?" with perfect recall and zero hashing. Its hard to imagine a faster method for that initial query, but of course it does nothing to help the second query out. Statistical details are important.
An additional consideration is that the initial "does it exist?" query doesnt have to be 100% accurate. False positives are the mainstay of several hashing algorithms (for instance, the Bloom (Filter) Hash) .. these algorithms focus on trading away significant space complexity for insignificant false positive rates (when the query returns "true" a slower method kicks in to prove that its true) .. if you only used 24-bits of a 32-bit key (a 2 megabyte bit table) but the collection itself only holds 1 million items, then false positives could be fairly rare while that bit table would actualy fit in a modern L3 memory cache, meaning very few cache misses.
Details...
How many items will this collection actualy hold?
Rockoon,
thanks for the answer.
Just a quick comment on the first piece of your answer: I will only be adding elements to the collection/array once, that is, when I'm parsing a file (I could also apply sorting or whatever here in case the algorithm I end up using needs it).
How often will the queries fail, generally speaking? I'd say very often.
The structure members are both QWORDs, DWORDs and strings at the moment (but as I mentioned before, they go below 50 bytes (the current structure size is 48 bytes)). The string member (an array of 24 chars.) will not be used to find items in the collection, at least not right now (the implementation might change in the future).
The algorithm/data structure type I end up using may not give off a lot of false positivies, though - none in fact, or perhaps I misunderstood your point there.
The collection will grow progressively (that is, as I add more and more stuff to the file which's then parsed into a collection of structures), so it may be 1000 today and 1 million in the future.
Regards,
Seb
Quote from: Seb on March 14, 2008, 07:07:20 PM
The collection will grow progressively (that is, as I add more and more stuff to the file which's then parsed into a collection of structures), so it may be 1000 today and 1 million in the future.
Is 1,000,000 an upper limit? I ask because currently you say the structure is 48 bytes per element so at a minimum you are looking at 48 megs of memory. You might run into design issues if both of these figures were to tripple (now over 400 megs.)
If the upper limit is indeed only 48 megs of data, then you could easily shoot for a 128 meg regular hash table with some smaller table leveraged to handle collisions.