Hashtable vs array

[DracoL1ch]

Edit:
Fuck this, wc3 has no solid base for any measurments. Turned out un-looped non-random access to array 10x times faster than access to hashtable. code provided by

Attached.

results:

Minding that that been 5k operations and yet it took <10 ms, it barely matters in real life, but it does matter for every snowflake.

Conclusion: hashtable is slower. but noone will ever notice that.


Fucking tired of that

function HashvsArray takes nothing returns nothing
    local integer i=1
    local integer key1='cnst'
    local integer key2
    local integer array ar
    set i=1
    loop
        set key2=GetRandomInt(1,8000)
        call SaveInteger(HY,key1,key2,23)
        set ar[key2]=23
        set i=i+1
        exitwhen i>5000
    endloop
    set i=1
    call StartPerfCounter()
    loop
        set key2=GetRandomInt(1,8000)
        set key2=LoadInteger(HY,key1,key2)
        set i=i+1
        exitwhen i>5000
    endloop
    call StopPerfCounter()
    set i=1
    call StartPerfCounter()
    loop
        set key2=GetRandomInt(1,8000)
        set key2=ar[key2]
        set i=i+1
        exitwhen i>5000
    endloop
    call StopPerfCounter()
endfunction

PerfCounter - self-made mix with win-timer clock

5k calls for value, only 2x diff between an array access time and hashtable access time.
which means less than 8 mcs per loop for hash and 4.24 ms per loop for array
Stop. Using. This. Argument. Your HDD is slower than hash. Theres totally no reason to avoid hashtables.

Note: been tested with disabled OP limit, else it kills the thread due to 30k limit

 

[Marcos_M]

So the hash lovers weren't wrong all this time?

 

[GhostWolf]

People using logic weren't wrong, no.

 

[Dr Super Good]

5k calls for value, only 2x diff between an array access time and hashtable access time.

We have known they have comparable speed to arrays ever since they were released. Arrays are still quite a bit faster.

I think your test makes them look so similar (only 2 times difference) because overhead is a large part of what is being measured. If you factor out that overhead you might find that hashtables are considerably slower. To put it in perspective the array access might be just taking 1ms of the total time while the hashtable access is taking 5ms, so that would be 5 times difference.

Additionally hashtables are subject to performance degradation if they contain too many mappings. So they might be fast with a low number of mappings (<<10,000) however they will be painfully slow with a lot of mappings (>>100,000). This is not really the case when used to substitute a single array, but is most certainly the case if it is used to simulate a large multi dimensional array.

A 5 times slower execution rate for every lookup can add up, especially in systems with a high frequency timer.

 

[DracoL1ch]

if someone has 100k+ values stored it's his own problem, not hashtable's one
what do you mean about overhead? first time access to hashtable takes more time yet it's only happens once. can't see how that affects anything

 

[Emm-A-]

does it matter, what kind of value you store in a hashtable slot? e.g. is it faster to handle and integer than an unit?

 

[DracoL1ch]

does it matter, what kind of value you store in a hashtable slot? e.g. is it faster to handle and integer than an unit?

one more op for checking type of passed handle, it won't be sensible. remember that any handle is a simple integer?

 

[Emm-A-]

sounds reasonable, but did you test it?

 

[GhostWolf]

It's amazing how stuck up people are here about nonsense that's irrelevant to anything, and that's really a key word in this discussion and many similar ones in the past. IT'S IRRELEVANT. Hashtables can be a 100 times slower and it will still not change anything, because 99% of the time you don't NEED speed (and this is NOT me saying they are slow).

I bet DSG never uses maps of any kind outside of Jass, because they are really slow and unreliable, right? No, not right. So stop spamming this god damn garbage you spout in every thread related to them, causing people who don't know better to never use them, and rely on old hacks instead. Thanks.

 

[Emm-A-]

why dont you tell us people, that do not know better, your superior knowledge instead of rage posting, which does not help anybody?

If you provided some insight, this would actually be helpful to understand, why you think that way.

 

[Aniki]

@GhostWolf, I don't mind people using hashtables when they are necessary (mapping big integers [StringHash, GetHandleId] to values, or requiring more storage than arrays could handle),
but the thing is that people ab-use hashtables for struct-ured data.

Even if they use the named keys (instead of hardcoded integers) feature of vJass, the result is not as readable as structs.

I bet DSG never uses maps of any kind outside of Jass, because they are really slow

It all depends on the implementation and data one is storing in them, but chance are they are slow.

 

[GhostWolf]

@Aniki, your example is invalid. Like I wrote previously, it's as if you intentionally wrote the hashtable code to be longer. You can use the same exact struct syntax and attach it with hashtables, meaning this is again IRRELEVANT.

Speed is irrelevant in most of the cases you'd use either way, so I don't see why you just need to keep spouting that, over and over and over again, but here, I'll reply just for you.

You - and this community - have some major perspective problems here.
What on earth is "slow" code?
Did someone define random access as some base standard and anything slower is invalid? why on earth are you even using vJass, with all of its extra garbage that it adds, if any tiny line of code it adds is probably heavier than random access?

Now, if you want to compare two atomic (in this context) operations, like random access and hashtable lookups, then sure, go for it, albeit it has been done and you can see the results in this thread.

But again, suppose hashtable lookup takes twice the time as random access, or heck, let's go with six times, because why not.
What information does this give you?
Do you have some table somewhere comparing the speed of random access to every other operation in Jass?
Do you know how many random accesses a call to CreateUnit is worth? maybe you should consider flattening loops, who knows, maybe their intrinsic code is heavier than random access.

To summarize, all of these benchmarks people here generally run don't MEAN anything in the real world. Just nice numbers in a virtual sand box which are, for the bazillion'th time, irrelevant.
When you (no one specific) start to compare ridiculous nonsense like locals versus arguments, I really have nothing more to berate you with without using very rude words.

I challenge you to write or find a REAL piece of code that suffers from any of your so called issues.
No, not a test demo created specifically to highlight what you say. Real code.

I just don't get you people.

Sorry if I come across as rude, but that was the goal.

 

[Aniki]

The point of my last post wasn't about speed (I've never even mentioned speed anywhere)... it was about readability!
In my opinion using structs results in more readable code, and ab-using hashtables results in less readable code. That's it.

 

[IcemanBo]

I'm also not really a fan of using hashtable for everything, especially when it's "only" used for making bigger sized arrays.
It's seems a bit wasted of the hashtable powers in some codes, as the amount of hashtables is limited. Though if one just use table instead, then all is fine I think and it can make code more readable.

For example, if you make data structures that aren't meant to have a lot of instances, then I find it good to to bind data directly to the callback-timer ( using table) just for each instance and readable code, instead of working with plain arrays and "extra" creating a linked list structure or something.

If you don't need looping through your data, or perma access to your elements, then why need of a list, if you can just run single timers and attach to it.

 

[GhostWolf]

Both of you are repeating the same example that @Aniki wrote (or in the second link, code that another person wrote in the same exact style), which uses arrays instead of a struct because...right, because you wanted to show that hashtables are less readable / require more code (which is purely a question of personal style, by the way, but you weren't even objective at being subjective, by giving a fake equivalency of code).
I am almost tempted to take your exact code and change it so it matches your so called clean struct code, just so you'd have it in front of your eyes.

I could quote your message from above that did indeed talk about speed, but that would be silly. As this topic is.

 

[IcemanBo]

I said using hashtable (table actually) + timer is better and more readable in some cases, actually, than creating extra data structure when it's not even needed.

 

[GhostWolf]

That's fine, but you keep tying up two different subjects, which is what I wrote, in more rude ways, three times by now.

1) Mapping an object to data, which started this topic.
2) Data storage - arrays, or a struct (which is the same but yey syntax sugar), or whatever you want.

For some reason it's as if you believe that the method of attachment means anything about the data you attach, which is obviously false - you can store your struct ID in a hashtable in the same exact way you attach it else-wise.
If anything, you are restricted in what you can attach with non-hashtable hacks, because they are indeed hacks (not to take any credit, they were brilliant at the time, just useless now).

 

[Aniki]

I am almost tempted to take your exact code and change it so it matches your so called clean struct code, just so you'd have it in front of your eyes.

Take this code and make it as readable as you can using hashtables and see what you end up with.

You can store your struct ID in a hashtable in the same exact way you attach it else-wise.

Agree. But people use hashtables in place of structured data, not structs, thats my grudge with hashtables.

 

[DracoL1ch]

Take this code and make it as readable as you can using hashtables and see what you end up with.



Agree. But people use hashtables in place of structured data, not structs, thats my grudge with hashtables.

whats unreadable there?
I have few considerations like caster normally stays in 0 or 2nd cell, target - 1 or 17th, tracked dummy - 42, etc etc. having declaration is just enough to read all your hashtable-related code like np, not to speak you'll upload it value to local variable before usage anyway, since it makes more sense.

so far I still didn't get what is "readable" code and how hashtables turns it "unreadable". but im a simple jasser, i've never used c/vjass and any other extensions

 

[IcemanBo]

But hashtables are limited. In big projects one might use quite some of them.
And why use a standalone hashtable with 2 keys (which is pretty powerful) when you don't even need it?
One can just go and use tables, so he can still use the hash methods, but doesn't require a hashtable for each single spell creation, or what ever else.

When I would import some spells, or minior system, I would not like it that each of them create their own hashtable, when they could easily avoid it.

I talk about vjass of course. Often people don't really need a hashtable, but just a bigger array size, so -> single table does the job.

edit: I never said not to use hashtables because of the hash methods, or so. I even encourage it in cases (see above). It's just the waste of hashtable resource that could bother me in cases.

 

[Dr Super Good]

what do you mean about overhead?

You are timing the loop itself? You should still get some time value if the following lines were removed...

set key2=LoadInteger(HY,key1,key2)
set key2=ar[key2]

And those lines are what you are trying to measure and compare!

one more op for checking type of passed handle, it won't be sensible. remember that any handle is a simple integer?

However it might increment/decrement the reference counter to prevent recycling. However that is likely trivial compared with JASS overhead.

Hashtables can be a 100 times slower and it will still not change anything, because 99% of the time you don't NEED speed (and this is NOT me saying they are slow).

It does matter for systems that are speed critical and need a lot of getting and setting of data with a high frequency tick. Seeing how most of the game processor time can end up being spent inside such systems, having them execute faster can make the difference between 60 FPS and only 50 FPS or less.

That said it only matters for such systems.

I bet DSG never uses maps of any kind outside of Jass, because they are really slow and unreliable, right? No, not right. So stop spamming this god damn garbage you spout in every thread related to them, causing people who don't know better to never use them, and rely on old hacks instead. Thanks.

You seem to be implying I said something I did not.

Outside of WC3 there are dozens of ways to map data depending on requirements. It is stupid to use a container like a hashmap or tree map when an array or list provides all that is needed even if it can be made to function in a similar way.

but the thing is that people ab-use hashtables for
struct
-ured data.

This is perfectly fine as well, as long as it is not in a performance critical section. The only time one needs to break away from hashtable usage to arrays is in extremely performance intensive sections. Or due to personal style preferences.

For neatness it is often better to map a struct instance to an object rather than the members of the struct. This provides encapsulation, keeping all struct members private, and avoids potential collisions. Some struct instances might need multiple objects to map to them which can only really be implemented in this way. This works well for trigger enhanced abilities in general as they mostly use an instance per cast based approach.

For neatness it is often better to map shared properties directly to an object rather than placing them in a struct and mapping that. This allows one to treat such properties as part of the object rather than depending on the implementation of some struct. This works well for mapping arbitrary values to object types, such as custom unit properties to unit types for use in a system.

What on earth is "slow" code?

JASS in general... To put it in perspective, the overhead from the JASS virtual machine is so high that complex mathematical operations such as trigonometric functions make no difference compared with simple logic implemented in JASS.

why on earth are you even using vJass

Mostly to bypass limits in the editor. Specifically to allow global variables to be defined anywhere is my most common reason.

What information does this give you?

That 1 hashtable access is similar to 6 normal accesses. Seeing how systems do a lot of access this can add up to a fractional speed slowdown. As you mentioned trivial in most cases, such as on ability cast or on damage. However when it comes to high frequency tick rate systems this is not so trivial.

Say a system uses 100 projectiles updating ~30 times a second, then that is 3000 ticks per second. Even if the performance difference with the hashtable mapped member version is as little as 10% longer (due to other, unrelated overhead being so large). This would mean that for the same 100 projectiles the hasthable version would take as much time as the array version running 110 projectiles. Seeing how such systems are often the cause of performance problems it is not trivial that one can get an extra 10% or so more objects for the same performance and this can result in fewer frames being dropped.

Do you have some table somewhere comparing the speed of random access to every other operation in Jass?

Someone was trying to make one at some stage...

Do you know how many random accesses a call to CreateUnit is worth?

CreateUnit is an abnormally slow function to call. Not only does it have a lot of overhead to create the unit and register it with all the game systems, but it then runs a pathing displacement check which by itself can cause the game to drop frames in a worst case scenario. Its performance is highly variable as a result of the pathing displacement check.

On the other hand comparing it with functions like Sine/Cosine, SquareRoot, etc would be useful. Chances are those functions execute faster than a hashtable lookup purely due to 1 less argument to resolve.

 

[GhostWolf]

Take this code and make it as readable as you can using hashtables and see what you end up with.

That code is a bit of a mess (mostly no new lines and udg_ names), beyond that I don't see the issue.
Do you not realize that code has the same lines it would have had had it used a struct, because IT'S UNRELATED TO THE MAPPING SCHEME you use, but the DATA?

let me highlight this.

This part of the code

call SaveReal(udg_Hash, h, 2, DMG)
call SaveReal(udg_Hash, h, 3, x1)
call SaveReal(udg_Hash, h, 4, y1)
call SaveReal(udg_Hash, h, 5, bj_RADTODEG * Atan2(y1 - y, x1 - x))
call SaveReal(udg_Hash, h, 6, x)
call SaveReal(udg_Hash, h, 7, y)

Is the equivalent to this in your code

local Message msg = Message.create()
set msg.message = message
set msg.repeat_count = repeat_count

And this

local unit u = LoadUnitHandle(udg_Hash, h, 1)
local real x = GetUnitX(u)
local real y = GetUnitY(u)
local real x1 = LoadReal(udg_Hash, h, 3)
local real y1 = LoadReal(udg_Hash, h, 4)
local real dis = LoadReal(udg_Hash, h, 99)+SPEED

Is the equivalent of this

local Message msg = t.data

There are two reasons why his code is longer.
1) He has more parameters, DUH.
2) He chose a different storage scheme, with arrays, rather than a struct.

This is again a matter of personal style - you can pick the way you structure your data, it is completely irrelevant to mapping objects.

/Edit @Dr Super Good
That post made me half giggle half headdesk, so I'll give you a pass this time.

 

[DracoL1ch]

You are timing the loop itself? You should still get some time value if the following lines were removed...

And those lines are what you are trying to measure and compare!

it takes less than microsecond, isn't handy to measure. since both loops are the same, loop's timing completely irrelevant.
It wasnt about measuring actual time, but in compare

 

[DracoL1ch]

On the other hand comparing it with functions like Sine/Cosine, SquareRoot, etc would be useful. Chances are those functions execute faster than a hashtable lookup purely due to 1 less argument to resolve.

oh drop that, one more "mov eax,[esp+04]" won't hurt at all

 

[Aniki]

That code is a bit of a mess (mostly no new lines and udg_ names), beyond that I don't see the issue.

You don't see the issue, really?

call SaveReal(udg_Hash, h, 2, DMG)
call SaveReal(udg_Hash, h, 3, x1)
call SaveReal(udg_Hash, h, 4, y1)
call SaveReal(udg_Hash, h, 5, bj_RADTODEG * Atan2(y1 - y, x1 - x))
call SaveReal(udg_Hash, h, 6, x)
call SaveReal(udg_Hash, h, 7, y)

I guess you understand the meaning of the keys 2, 3, 4, 5, 6, and 7 just by reading the above lines...

Do you not realize that code has the same lines it would have had had it used a struct, because IT'S UNRELATED TO THE MAPPING SCHEME you use, but the DATA?

This is again a matter of personal style - you can pick the way you structure your data, it is completely irrelevant to mapping objects.

Do you not realize that my point is not about how one retrives his struct instance in a timer callback (array, hashtable, "old hacks "), my point is about using structs in the first place!

 

[DracoL1ch]

hell. that totally off the point. I dont use structs at all, yet im able to maintain one of biggest alive projects. once you look below, you'll find out which field is for.
read the first message again. this topic is about those who claims hash or anything else being slow. many of old guys uses old, non-checked data from random members. I used to be like that. We should stop that and actually do fact-checking.
Coding style isn't belong to lab

 

[Dr Super Good]

it takes less than microsecond, isn't handy to measure. since both loops are the same, loop's timing completely irrelevant.
It wasnt about measuring actual time, but in compare

Except you cannot compare them because you do not know what they are to start with...

You have given us two times...
X + A (the array test time)
X + B (the hashtable test time)
With the result that X + B ~= 2 * (X + A) and then jump to the conclusion...

only 2x diff between A and B.

Which is not right as the mathematics make no sense.

Nothing sensible is being compared unless you can remove X. Hence repeat the experiment for a loop without the overhead of A or B to find X, which can be considered a scientific control to some extent as it is the minimum time spent before doing anything. Then subtract X from the current results to get the correct approximate time spent to execute a random array lookup and a random hashtable lookup. The result will be a lot bigger than 2 times.

oh drop that, one more "mov eax,[esp+04]" won't hurt at all

I do not understand where you get that assembly from. JASS does not work with assembly directly, instead running in a sort of virtual machine. Every named argument has to be parsed at run time and then looked up in a huge map, hence why it is so slow.

 

[DracoL1ch]

loop is consistant inbetween, can't see how you can't understand that A==2B is proper evaluation.
loop + 500A == loop + 500B*2
we know that looping doesn't take 2 times longer just because it contains hash somewhere inbetween ops, so it can be removed.
explain any situation where it cannot be truth.
also that's been 3 tests in a row, so values kept growing in each time. very 1st run went almost the same, yet I removed it to avoid "1st access" time issue.

goddamn, do the fucking math yourself, test values yourself, im fucking tired of that, DSG. u keep coming, giving 0 fucks about reality, opressing some senseless "you can't assume loops are identical" shit etc.

 

[Aniki]

So Jass's hashtables are ~2x slower than Jass's arrays... that somewhat implies that Blizzard's hashtable implementation is pretty good, right?

@DracoL1ch, do you know what kind of collision resolution hashtables do in Jass?
I.e what happens when 2 things end up in the same bucket of the hashtable: 1) each bucket has a linked list of items (separate chaining), or 2) "probing".

This is not really important from a Jass's perspective but I am kind of curious (I could try to implement the worst hashtable one day!) =).

And another question, how does Blizzard hash the two keys (parent, child)? Do they make a single 64bit key and hash that or something smarter/else?

 

[Deleted member 219079]

good

No. This loop is rigged in your face. Unroll it and come again.

Here:

mapping big integers [
StringHash, GetHandleId
] to values

 

[DracoL1ch]

im not an expert in that. when Leandro saw that, he said Blizz used very lazy approach

Spoiler: skype

Leandro Teles: btw, talking about hashtables, do you know what I found, Jass hashtables don't hash anything at all hahaha
DracoL1ch: aren't they are vtables?
Leandro Teles: well. they are hashtables, but a hashtable is supposed to have a hash function which will return a unique value for each key you pass it to avoid collisions
Leandro Teles: for example, object data is stored in hashtables as well, and the hash function is that IntegerHash function from my code
DracoL1ch: heh you mean their naming is misleading
Leandro Teles: I wouldn't say misleading, usually a hashtable is an array of linked lists, which is exactly what the jass hashtable does
Leandro Teles: but the difference is that it doesn't use any hashing function, it just takes the value directly, extracts the last 3 or 4 bits, and uses that as an array index
Leandro Teles: make a search on how hashtables work and you will understand
Leandro Teles: it's pretty much a standard c++ hashtable, an array of linked lists
Leandro Teles: it takes the key value, extracts the last bits, and uses that as the array index
Leandro Teles: and then starts iterating the linked list at that key
DracoL1ch: ok got it, I thought at first there are collisions between a keys with similar bytes
Leandro Teles: there are, but a hashtable usually has a hashing function associated to return unique values for every different key, thus avoiding collisions
Leandro Teles: but JASS hashtables don't have any hash function
DracoL1ch: so we have collisions much more often than supposed to?
Leandro Teles: yes

 

[Aniki]

So... the two arguments (parentKey, childKey) from

native  SaveInteger takes hashtable table, integer parentKey, integer childKey, integer value returns nothing

are converted to a hash with the "IntegerHash function from my (leandrotp) code", and then only the lower 3 or 4 bits are used for the index of the bucket.
Does that mean that a hashtable has only 2^4 = 16 buckets?

And each bucket has a linked list (separate chaining)... I thouh linked lists aren't that fast? So I guess Blizzard's linked lists are somehow amazingly fast?

Thanks anyway, that was really interesting to read =).

 

[Deleted member 219079]

im not an expert in that

Attached.

 

[Dr Super Good]

loop is consistant inbetween, can't see how you can't understand that A==2B is proper evaluation.

But you have given...
X + B ~= 2 * (X + A)

loop + 500A == loop + 500B*2

Where does 500 come from!?

we know that looping doesn't take 2 times longer just because it contains hash somewhere inbetween ops, so it can be removed.

Actually it might, since you have not tested otherwise due to a lack of control.

explain any situation where it cannot be truth.

With JASS because JASS is a very complex language that runs in a high level virtual machine and resolves every named type using an internal map.

also that's been 3 tests in a row, so values kept growing in each time. very 1st run went almost the same, yet I removed it to avoid "1st access" time issue.

You did not correct for that by running an access before the tests? Or prove that it exists with another set of tests? This is not at all scientific!

goddamn, do the fucking math yourself, test values yourself, im fucking tired of that, DSG. u keep coming, giving 0 fucks about reality, opressing some senseless "you can't assume loops are identical" shit etc.

The loops are identical, but they do have a substantial timing overhead due to being JASS. You need to remove the timing overhead of the loop to get the actual timing of what is being tested. One can then do a proper comparison. What you are doing currently you might as well throw in another 10,000 different function calls in-between and then say that both are the same as the timings are then within measuring error.

Until then your statement on timing is off, and I can assure you the difference is more than 2 times as slow. Maybe less than 10 times as slow but still grater than 2 times as slow.

Unless you have hacked WC3 so much as to remove loop overhead entirely by adding a proper JASS compiler that unwinds such constant loops. I do not know what the measuring tool you made has changed with the JASS virtual machine so that is a possibility in which case I accept your results as correct.

im not an expert in that. when Leandro saw that, he said Blizz used very lazy approach

They are called hashtables because they are obviously based on Game Caches, which were used before hashtables for the same functionality, where string hashes were used. Also a hashtable maps data to a hash and a hash's definition is such that a lot of data can fulfil it. Even Handle IDs fulfil it to some extent.

And each bucket has a linked list (separate chaining)... I thouh linked lists aren't that fast? So I guess Blizzard's linked lists are somehow amazingly fast?

Native linked lists are amazingly fast compared with the amount of time the JASS virtual machine spends hashing argument names. The linked lists also only really get used if a lot of collisions occur which requires a lot of values to be stored. Hence what I said earlier.

 

[DracoL1ch]

why would I? goddamit, whole this topic barely matters anything scientific, except preventing usage of "slow" word next to any thing people may come with. it doesnt matter if I removed first access, if there's loop overheat, if there's bad weather on moon or something else.

 

[Dr Super Good]

why would I? goddamit, whole this topic barely matters anything scientific, except preventing usage of "slow" word next to any thing people may come with. it doesnt matter if I removed first access, if there's loop overheat, if there's bad weather on moon or something else.

So you are saying that they are some what slower than array accesses? We already knew this before the final patch went live that added them...

WC3C lot said that they are roughly 3 times as slow as array lookups back then. This was done with FPS counter measurement deltas so was quite inaccurate.

Fact is they are quite a bit slower than a normal array access. Fact is it does matter in performance critical code, like all optimizations do such as shorter variable names due to the very definition of performance critical code. Fact is that in most code it does not matter as most code is nowhere near performance critical. Ultimately usage is mostly down to personal style preferences.

If someone wrote a proper optimizing JASS pre-compiler then it would matter event less. Even Vexorian's optimizer lacks proper automatic inline optimization, or compile time resolution and inlining of constants.

That post made me half giggle half headdesk, so I'll give you a pass this time.

I sometimes really worry about people who fail to see a difference between a hash map and an array. It is common exam question of sorts as well...

Long before hashtables I wrote my own hashtable style mapping for 1 index. It used an array and modulus 8000 with next index collision handling. I was very happy with the way it worked, although many people called me an idiot for doing so for some reason. Slow as hell but avoided the problems with the game cache solutions one had back then. At the time the recommended solution from the WC3C lot was to not leak handle IDs and make maps that never needed more than ~8192 handles.

 

[Deleted member 219079]

why would I? goddamit, whole this topic barely matters anything scientific, except preventing usage of "slow" word next to any thing people may come with. it doesnt matter if I removed first access, if there's loop overheat, if there's bad weather on moon or something else.

Could you give output of the code I attached?

 

[DracoL1ch]

So you are saying that they are some what slower than array accesses? We already knew this before the final patch went live that added them...

I said that its miserably minor difference which should be ignored for the sane of humanity

Could you give output of the code I attached?

no time to run this thing

 

[Dr Super Good]

I said that its miserably minor difference which should be ignored for the sane of humanity

Except you have little evidence it is minor as you are using the wrong mathematics and have no control.

The hashtable loop takes twice as long to run as the array loop. Except that could mean anything from the hashtable access taking twice as long as an array access (assuming no loop overhead), to the hashtable access being infinitly slower than the array lookup (assuming array lookup is instantaneous). In the first case it is very minor, in the second case it makes a huge difference.

Hashtable lookup is comparable to array lookup, people proved that a long time ago. However they quantified it at 3-4 times slower.

 

[DracoL1ch]

fuck that, im out. somehow loop and randoming numbers affects perfomance in a strange way. wc3: no consistency whatsoever.
first post updated

 

[Aniki]

Accessing the elements of an array in a consecutive order is "cache friendlier" for the processor than accessing the elements in a random order which probably incurs a lot of cache misses.

So you shouldn't be "annoyed" by the results at all, in my opinion, because modern processor are rather complex and doing benchmarks is also very hard.

 

[DracoL1ch]

Accesssing the elements of an array in a consecutive order is "cache friendlier" for the processor than accessing the elements in a random order which probably incurs a lot of cache misses.

So you shouldn't be "annoyed" by the results at all, in my opinion, because modern processor are rather complex and doing benchmarks is also very hard.

well as we all know jass uses virtual machine with many overheads (every given type is checked to fit the type function awaits for, etc etc)
for instance LoadInteger(HY,'cnst',12) will run a check through all variables, searching for HY, then it will re-check if it's hashtable type. then it will proceed to cast rest arguments one by one, re-cheking if they are integers and stuff. only then game goes to actually heap and retrieve data.
meanwhile array access pretty much static through the line, game only have to find variable and check "it's array".
this difference may be big enough, althought it's yet isn't big deal at all. I've seen 100s infinity loops behind WC3 window, some of them really heavy, yet game itself pretty fluent even with heavy jass assets inside. amazing thing is - doesnt matter if hash or array, it still won't make difference. even tho it's 10 times longer.

 

[MyPad]

Hashtables vs Arrays,
Handles vs integers,

Why not combine them together?

Speed is their difference.
Structs and hashtables,
can they be combined?

I think so

And structs
are arrays, only being neater (or more neat).

A global hashtable,
a lot of structs,

just some sort of attachment is
more than enough.

To moderators, moderators everywhere:
I apologize for breaking a rule,
if I did, but I wanted to comment

and I greet you all a happy

New Year.

 

[Deleted member 219079]

We already combine them. Large numbers are turned into array indexes with hashtables. E.g. local MyStruct myInstance = myTable.integer[GetIssuedOrderId()]

To moderators, moderators everywhere:
I apologize for breaking a rule,

You broke a rule? Nice!

 

[DracoL1ch]

issue is structs is for those who actually works with some compilator while im using raw input and cant afford compiling stuff everytime to check something

unless you're gonna do 1000+ requests per given frame you shouldnt care about speed at all

 

[MyPad]

unless you're gonna do 1000+ requests per given frame you shouldnt care about speed at all

I think that settles the hashtable vs array issue.

 

[GhostWolf]

It's not 1000+, it's not any deterministic number. It totally depends on one's code, and one should CHECK this, instead of defaulting to nonsense arguments like "array access is X times faster than hashtables".

While I keep saying that this argument is stupid, it's not because it never matters, it's because the people that say it matters do so generally, without ever testing their own claims and seeing WHERE it matters.

But again, in a community of special snowflakes, that write totally unreadable nonsensical code that has zero uses, and is filled with useless micro optimizations, I am not sure that writing something like this helps.

 

[DracoL1ch]

It totally depends on one's code, and one should CHECK this

indeed, but simple check "do you use those natives about 1000 times per trigger fire?" is faster than checking and gives all the same answer ("you shoulnd't bother bout it").

 

[GhostWolf]

Definitely, it's just the general response to the general argument.

In practice, this will almost never matter, and one should write CLEAN and READABLE code.

 

[Deleted member 219079]

^ I see lots of C++ people saying "don't help the compiler", it's true for C++, but JASS is slow and JassHelper only inlines, nothing else.