11 Sep, 2009, JohnnyStarr wrote in the 1st comment:
Votes: 0
iHash = vnum % MAX_KEY_HASH;        
pObjIndex->next = obj_index_hash[iHash];


I believe the MAX_KEY_HASH is 1024.
So if i had a vnum of 3001, why would i want the remainder of if i divided it by 1024?
Obviously I'm missing something :redface:
Would someone mind explaining this in detail?
Thanks.
11 Sep, 2009, kiasyn wrote in the 2nd comment:
Votes: 0
Its choosing a hash bucket.

the hash is an array of size MAX_KEY_HASH, in this case 1024.

Each member in the array is a list, so

getObjByVnum( int vnum ) {
bucket = vnum % MAX_KEY_HASH;
iterate over obj_index_hash[bucket] as obj
return obj if obj.vnum == vnum
}


is a lot quicker than:
getObjByVnum( int vnum ) {
iterate over obj_index_list as obj
return obj if obj.vnum == vnum
}


because the hash will have less members in it, but the list has to iterate over the entire set of rooms.
11 Sep, 2009, JohnnyStarr wrote in the 3rd comment:
Votes: 0
ok, so each bucket has "sets" of elements, instead of checking
each element, we examine sets with similar vnum values?
11 Sep, 2009, kiasyn wrote in the 4th comment:
Votes: 0
not necessarily, just all that end up with the same remainder
11 Sep, 2009, ghasatta wrote in the 5th comment:
Votes: 0
It's a convenient way to subdivide your really big list into smaller buckets, so that you don't have to traverse the entire list when searching for an object with a specific index.
11 Sep, 2009, kiasyn wrote in the 6th comment:
Votes: 0
Eg:
#!/usr/bin/ruby

MAX_KEY_HASH = 1024

obj_index_hash = Array.new(MAX_KEY_HASH) { Array.new }

1.upto(30000) do |i|
bucket = i % MAX_KEY_HASH
obj_index_hash[bucket].push i
end

puts "Bucket 2"
p obj_index_hash[2]

puts "Bucket 5"
p obj_index_hash[5]


Output:
Bucket 2
[2, 1026, 2050, 3074, 4098, 5122, 6146, 7170, 8194, 9218, 10242, 11266, 12290, 13314, 14338, 15362, 16386, 17410, 18434, 19458, 20482, 21506, 22530, 23554, 24578, 25602, 26626, 27650, 28674, 29698]
Bucket 5
[5, 1029, 2053, 3077, 4101, 5125, 6149, 7173, 8197, 9221, 10245, 11269, 12293, 13317, 14341, 15365, 16389, 17413, 18437, 19461, 20485, 21509, 22533, 23557, 24581, 25605, 26629, 27653, 28677, 29701]
12 Sep, 2009, elanthis wrote in the 7th comment:
Votes: 0
Stary, just go read up on how hash tables work. It will answer the question you have now and it will answer a lot of questions you don't have yet. :)

http://en.wikipedia.org/wiki/Hash_table
12 Sep, 2009, Scandum wrote in the 8th comment:
Votes: 0
Just get rid of the linked list and hash table and go for an array.

ROOM_INDEX_DATA * room_index[MAX_VNUM];

get_obj_index(int vnum)
{
if (vnum <= 0 || vnum >= MAX_VNUM)
{
return NULL;
}
return room_index[vnum];
}


It'll be faster to lookup, faster to parse, and cost less memory if more than 25-30% of the vnums are used.
12 Sep, 2009, David Haley wrote in the 9th comment:
Votes: 0
Scandum said:
and cost less memory if more than 25-30% of the vnums are used.

Can you show us the calculations that led you to that conclusion?
12 Sep, 2009, elanthis wrote in the 10th comment:
Votes: 0
A straight array will most certainly not use less memory with only 30% utilization, unless you're talking about a very small array (dozens of entries versus thousands) or if your hash table was written by an idiot. I don't know what you mean by faster to parse. And faster to lookup is something you may be surprised about, because a well written hash table will have far better cache locality than a big array, and can be way faster if you do frequent lookups due to the greatly reduced cache miss rate. Again, though, only with a large vnum range – if the range is very, very small, a straight array is definitely the better way to go.

The hash table is also far better if you ever do find yourself needing to just iterate over all rooms – so long as you don't care about the orders they're in – because you don't need to iterate over a mostly empty array (and a mostly full array will still have more holes than a mostly full good hash table will).

Computer scientists came up with hash tables to replace straight arrays for a reason. There are times when the straight array is better, but the overwhelming odds are this isn't one of them.

Simple math:
32-bit pointer = 4b
max vnums = 10,000
memory use of array = 40,000b
hash bucket count = 513 **
memory use of hash table + linked list: ~4,104b (assuming relatively even distribution, load factor 1)
memory use of hash table + linked list: ~12,312b (assuming relatively even distribution, load factor 3)

So not only is it less memory (by an entire order of magnitude at a load factor 1), but 4k far more easily fits in your data cache than 40k. If your hash bucket linked list allocator pulls from a pool of lmemory versus using straight malloc then you can ensure that 4,104 bytes are all allocated in a single contiguous chunk and you can even instruct the compiler to preload the whole chunk before accessing it in any loops. At 32 byte cache lines, that's a maximum worst-case 129 cache misses for the hash table versus 1,250 cache misses for the array. Iterating over the list of vnums would take a fixed 10,000 loop iterations on the array versus a minimum of 513 for the hash table, and an average case maximum of the actual room count (with a good hash function).

Assuming all data is in cache, a straight lookup of the array is faster than the hash table by several instructions. In that case and only in that case does the array approach have a clear advantage, but then those several instructions will be completely negated by a massive amount if there's so much as a single cache miss.

Of course, if you have more than a 10,000 limit on vnums, the hash table will outpace the array at an exponentially increasing rate.

** I picked a bucket size of 513 arbitrarily. You want it to be no less than the number of actual rooms you have divided by 3 (that is, you want no higher than a load of 3) in general. You also almost certainly want to use a prime number instead of a power of 2, because a modulus with a power of 2 is going to give you poor distribution on average. If you have an actual 50,000 rooms (independent of whatever maximum vnum number you support) then you'd want to use a bucket count like, say… 20,887.

All that said, there are even more intelligent ways to break up the room hierarchy, ways in which might even make straight arrays more useful. For example, a vnum could be two parts, one part the area number and one part the room numbers. So the 8th room in the 5th area might be 2053 (using the high and low bytes of a 16-bit number, as an example). You can look up the area in a simple array and then look up the room in the per-area room list using a simple array. If your area and room numbers are sparse, however, (which is likely to happen if you remove and add rooms a lot and don't want to reuse room numbers to avoid incorrect reference accidents), then the straight arrays go back to being a poor choice.

I guess the moral of the story is that you have to actually know what the hell you're doing or you're not going to have any way to determine whether Scandum's approach or our approach is better for your specific needs, and we can't really give you the best answer without intimately knowing your specific needs. Good luck. ;)
12 Sep, 2009, David Haley wrote in the 11th comment:
Votes: 0
Oh come on Elanthis, I was going to at least give him a chance to defend himself…
12 Sep, 2009, ghasatta wrote in the 12th comment:
Votes: 0
+1
12 Sep, 2009, JohnnyStarr wrote in the 13th comment:
Votes: 0
Ok, i do appreciate the input.
And the benefit isn't hard to see.
13 Sep, 2009, Scandum wrote in the 14th comment:
Votes: 0
David Haley said:
Can you show us the calculations that led you to that conclusion?

Not even going to respond to the load of bs Elanthis came up with.

If your max vnum is 20.000 and you have 10.000 rooms, use a double linked list, and a 3000 bucket hash table with both tail and head pointers, assuming 4 byte per pointer, you need 10.000 * 12 bytes for the linked list, and 3.000 * 12 bytes for the hash table. That's a total of 120K + 36K = 156K. Using an array you'd use 20.000 * 4 which adds up to 80K of memory. So roughly 50% less memory usage at 50% utilization.

Looking up an index in the array is one index lookup with an array, looking up the hash table you first need to generate the key, next lookup the index in the hash table, then loop through a linked list. Needless to say that the straight forward array lookup will be faster.

For looping though every room you can go through the array directly, but if performance is a concern you can loop through the area list, then loop through the array from the area's low vnum to the area's high vnum for each area.
13 Sep, 2009, David Haley wrote in the 15th comment:
Votes: 0
Thanks for explaining your reasoning. In light of this, would suggest that people read Elanthis's fairly detailed explanation of what's going on, perhaps in particular the bit about how a stupidly designed hash table would of course be memory-hungry.

For example, you would certainly not store 3 pointers for each bucket of the hash table even when empty. And there's also no reason to use a doubly-linked list.

So if we use singly-linked lists, we end up with 3,000 * 4 = 12k bytes for the buckets themselves, and then each stored element costs 8 bytes (4 for the pointer to the room, and 4 for the pointer to the next element) – meaning that we get 10,000 * 8 = 80k. The total is 92k, meaning that at 50% utilization, the hash table doesn't really use that much more. But we were talking about 30% utilization… meaning that the array would still use 20,000 * 4 = 80k, whereas the hash table would use 3,000 * 4 + 6,666 * 8 = 12k + 53k = 65k.

As Elanthis said, the right answer depends very highly on the situation. But, it is quite clear that an intelligently designed hash table is more memory efficient than an array at sparse utilization. In fact, you could work out a formula to determine where exactly the break-even point is.
13 Sep, 2009, Scandum wrote in the 16th comment:
Votes: 0
I guess a singly-linked list would suffice, putting the break even point somewhere at 42% utilization. The array would still be faster.
0.0/16