|
Joined: Feb 2003
Posts: 2,812
Hoopy frood
|
OP
Hoopy frood
Joined: Feb 2003
Posts: 2,812 |
I notice that enumerating $ialchan() is awfully slow compared to $ial(). So slow in fact, that it is twice faster to perform a WHO #chan or /ialfill and scrape data from the RAW numeric responses.
Some experiments to perform.
1) Connect to freenode and join #freenode (a large channel).
2) Populate the IAL /ialfill #freenode
3) Enumerate $ial(*,%i) //var %i = 1, %n = $ial(*,0), %cnt = 0, %ticks = $ticks | WHILE (%i < %n) { if ($ial(*,%i)) { inc %cnt } | inc %i } | echo -a * %cnt of %n - $calc($ticks - %ticks) ms. Result: * 1575 of 1577 - 140 ms.
4) Enumerate $ialchan(*,#,%i) //var %i = 1, %n = $ialchan(*,#,0), %cnt = 0, %ticks = $ticks | WHILE (%i < %n) { if ($ialchan(*,#,%i)) { inc %cnt } | inc %i } | echo -a * %cnt of %n - $calc($ticks - %ticks) ms. Result: * 1575 of 1577 - 9844 ms.
Now join several very large channels (from /list) and /ialfill them too, then repeat the last command (4).
You will find that $ialchan() gets slower and slower the larger that the server's $ial() becomes. * 7289 of 9374 - 1279 ms. $ial() * 1205 of 1580 - 16973 ms. $ialchan()
- The effects appear to be identical when retrieving properties of $ial() and $ialchan().
//var %i = 1, %n = $ial(*,0), %cnt = 0, %ticks = $ticks | WHILE (%i < %n) { if ($ial(*,%i).account) { inc %cnt } | inc %i } | echo -a * %cnt of %n - $calc($ticks - %ticks) ms. //var %i = 1, %n = $ialchan(*,#,0), %cnt = 0, %ticks = $ticks | WHILE (%i < %n) { if ($ialchan(*,#,%i).account) { inc %cnt } | inc %i } | echo -a * %cnt of %n - $calc($ticks - %ticks) ms.
The above commands will count how many users are logged into a nickserv account, globally or for the specific channel.
Well. At least I won lunch. Good philosophy, see good in bad, I like!
|
|
|
|
Joined: Feb 2003
Posts: 2,812
Hoopy frood
|
OP
Hoopy frood
Joined: Feb 2003
Posts: 2,812 |
It is indeed faster to use if ($ial(*,%i).nick ison $chan) than to use $ialchan() at all.
//var %i = 1, %n = $ial(*,0), %cnt = 0, %ticks = $ticks | WHILE (%i < %n) { if ($ial(*,%i).nick ison #) { inc %cnt } | inc %i } | echo -a * %cnt of %n - $calc($ticks - %ticks) ms. Result: * 1578 of 10545 - 1794 ms.
Well. At least I won lunch. Good philosophy, see good in bad, I like!
|
|
|
|
Joined: Feb 2003
Posts: 2,812
Hoopy frood
|
OP
Hoopy frood
Joined: Feb 2003
Posts: 2,812 |
Is the IAL a semi-sorted array of linked lists, with each bucket being the first character of the nickname?
Well. At least I won lunch. Good philosophy, see good in bad, I like!
|
|
|
|
Joined: Jan 2004
Posts: 2,127
Hoopy frood
|
Hoopy frood
Joined: Jan 2004
Posts: 2,127 |
This shows that $ialchan() is getting increasingly slower as it works its way deeper in the list, so the slowness isn't noticed in channels of just a couple hundred. //var %i = 1, %n = $ialchan(*,#,0), %cnt = 0, %ticks = $ticks , %t2 = $ticks | WHILE (%i < %n) { if ($ialchan(*,#,%i)) { inc %cnt } | inc %i | if (*00 iswm %i) { echo -a %i * %cnt of %n - $calc($ticks - %ticks) ms. recent $calc($ticks -%t2) ms | var %t2 $ticks } } | echo -a * %cnt of %n - $calc($ticks - %ticks) ms.
Result in newest beta: 100 * 99 of 1540 - 0 ms. recent 0 ms 200 * 199 of 1540 - 31 ms. recent 15 ms 300 * 299 of 1540 - 63 ms. recent 32 ms 400 * 399 of 1540 - 125 ms. recent 62 ms 500 * 499 of 1540 - 219 ms. recent 94 ms 600 * 599 of 1540 - 328 ms. recent 109 ms 700 * 699 of 1540 - 484 ms. recent 156 ms 800 * 799 of 1540 - 687 ms. recent 203 ms 900 * 899 of 1540 - 952 ms. recent 265 ms 1000 * 999 of 1540 - 1248 ms. recent 296 ms 1100 * 1099 of 1540 - 1623 ms. recent 375 ms 1200 * 1199 of 1540 - 2075 ms. recent 452 ms 1300 * 1299 of 1540 - 2590 ms. recent 515 ms 1400 * 1399 of 1540 - 3198 ms. recent 608 ms 1500 * 1499 of 1540 - 3885 ms. recent 687 ms * 1539 of 1540 - 4181 ms.
|
|
|
|
Joined: Dec 2002
Posts: 5,420
Hoopy frood
|
Hoopy frood
Joined: Dec 2002
Posts: 5,420 |
Thanks for your bug report. $ialchan() builds a new list by combining two existing lists, the IAL and the nick list of a specific channel, and then indexes that list from 0 to N. The reason it is slow is because it has to do this every time it is called. Both IAL and nick list are hash tables, so are fairly instant. However, the amount of work $ialchan() needs to do, every time it is called, is what slows it down. The only solution would be for $ialchan() to cache recent results and to reference them if nothing has changed in the interim, although this would slow down $ialchan() initially and use more memory. This has been added to my to-do list as a feature suggestion.
|
|
|
|
Joined: Dec 2002
Posts: 5,420
Hoopy frood
|
Hoopy frood
Joined: Dec 2002
Posts: 5,420 |
It is indeed faster to use if ($ial(*,%i).nick ison $chan) than to use $ialchan() at all. That is not the same as $ialchan() :-) $ialchan() builds a new list by combining two lists, the IAL and the nick list, and then indexes that list from 0 to N. A similar approach in a script would be the following, which you can run by typing /test on a channel: test {
var %n = $testex(#,0)
echo n: %n
var %i = 1
while (%i <= %n) {
echo nick: $testex(#,%i)
inc %i
}
}
testex {
var %chan = $1
var %k = $2
var %i = 1
var %n = $ial(*,0)
var %cnt = 0
while (%i <= %n) {
var %nick = $ial(*,%i).nick
if (%nick ison %chan) {
inc %cnt
if ((%k > 0) && (%cnt == %k)) return %nick
}
inc %i
}
if (%k == 0) return %cnt
}
|
|
|
|
Joined: Apr 2004
Posts: 871
Hoopy frood
|
Hoopy frood
Joined: Apr 2004
Posts: 871 |
Just FWIW, I would presume that in the general case it would be more efficient to iterate over $nick() rather than $ial() in the combination? That is: test {
var %n = $my_ialchan(*,#,0)
echo n: %n
var %i = 1
while (%i <= %n) {
echo nick: $my_ialchan(*,#,%i).nick
inc %i
}
}
my_ialchan {
var %mask = $1
var %chan = $2
var %k = $3
var %i = 1
var %n = $nick(%chan,0)
var %cnt = 0
while (%i <= %n) {
var %addr = $ial($nick(%chan,%i))
if ((%addr != $null) && (%mask iswm %addr)) {
inc %cnt
if ((%k > 0) && (%cnt == %k)) return $ial($nick(%chan,%i)) [ $+ [ $iif($prop,. $+ $prop) ] ]
}
inc %i
}
if (%k == 0) return %cnt
} Presumably, $ial(nick) is a very fast lookup and the 'iswm' test needs to happen even for iteration over $ial(). That also means that in this case, no intermediate list would need to be created I think - depending on the implementation, the $ial(nick) lookup may even be as simple as a direct pointer dereference. Would the most straightforward conversion to C of this approach be faster than the current one, or am I missing something? I am just curious (I have no stake in this, and would recommend that the examples used so far be rewritten to use $ial($nick()).prop anyway).. Edit: for completeness of the story: my assumption is that the current reason for the creation of the list is what is hidden in the 'ison' part of your script, i.e. the (expensive?) check to see whether the IAL entry is relevant for the given channel - going the other way around would then sidestep that part. Edit 2: oh and I am also assuming that basic iteration through $nick() is fundamentally as fast as basic iteration through $ial(), which I think/hope is reasonable..
Saturn, QuakeNet staff
|
|
|
|
Joined: Dec 2002
Posts: 5,420
Hoopy frood
|
Hoopy frood
Joined: Dec 2002
Posts: 5,420 |
I would presume that in the general case it would be more efficient to iterate over $nick() rather than $ial() in the combination? That depends... iterating over $nick() is slower in some cases beause the IAL match routine is slightly more complex than the nick list match routine, even though both use hash tables. So a large number of IAL items are needed before it starts to make a difference.
|
|
|
|
Joined: Feb 2003
Posts: 2,812
Hoopy frood
|
OP
Hoopy frood
Joined: Feb 2003
Posts: 2,812 |
(necro'd) Btw, I thought I'd point out that $ial() also, to a lesser extent, experiences a similar slowdown when enumerating through $ial(*,%i) as %i increases in size. I'm aware this is the result of the IAL being a hash table, but I was wondering if it could also be optimized like it was in v7.48-#28 ... When nick/mask is exactly an asterisk '*' then jump-to the Nth entry directly. Assuming that's possible in your hashtable implementation. Currently, to get to $ial(*,10000), mIRC internally scans the first 9,999 IAL entries to make sure they match '*' (which we can assume they always will) before returning the 10,000th entry. __ //var %i = 1, %n = $ial(*,0), %ticks = $ticks | while (%i <= %n) { noop $ial(*,%i) | inc %i } | echo -a * ial test: %n entries - $calc($ticks - %ticks) ms.
* ial test: 100 entries - 0 ms.
* ial test: 500 entries - 16 ms.
* ial test: 1000 entries - 31 ms.
* ial test: 2000 entries - 109 ms.
* ial test: 3000 entries - 156 ms.
* ial test: 4000 entries - 234 ms.
* ial test: 5000 entries - 312 ms.
* ial test: 6000 entries - 562 ms.
* ial test: 7000 entries - 734 ms.
* ial test: 8000 entries - 905 ms.
* ial test: 9000 entries - 1170 ms.
* ial test: 10000 entries - 1495 ms.
Well. At least I won lunch. Good philosophy, see good in bad, I like!
|
|
|
|
Joined: Dec 2002
Posts: 5,420
Hoopy frood
|
Hoopy frood
Joined: Dec 2002
Posts: 5,420 |
That is because $ial() needs to iterate with some combinations of parameters. I looked into this the last time you requested that $ial() be speeded up and I optimized it then as best as I could.
|
|
|
|
Joined: Feb 2003
Posts: 2,812
Hoopy frood
|
OP
Hoopy frood
Joined: Feb 2003
Posts: 2,812 |
Ok, thanks. Then let me make another more proposition... Store the last lookup's location pointer, so that subsequent calls to $ial(%entry).properties can go faster. var %entry = $ial(*,%i)
var %nick = $ial(%entry).nick
var %user = $ial(%entry).user
var %host = $ial(%entry).host
var %acct = $ial(%entry).account
var %away = $ial(%entry).away
var %gecos = $ial(%entry).gecos
var %id = $ial(%entry).id
var %mark = $ial(%entry).mark I presume that each lookup is stateless and an ordeal of its own.
Well. At least I won lunch. Good philosophy, see good in bad, I like!
|
|
|
|
Joined: Aug 2003
Posts: 319
Pan-dimensional mouse
|
Pan-dimensional mouse
Joined: Aug 2003
Posts: 319 |
Ok, thanks. Then let me make another more proposition... Store the last lookup's location pointer, so that subsequent calls to $ial(%entry).properties can go faster. var %entry = $ial(*,%i)
var %nick = $ial(%entry).nick
var %user = $ial(%entry).user
var %host = $ial(%entry).host
var %acct = $ial(%entry).account
var %away = $ial(%entry).away
var %gecos = $ial(%entry).gecos
var %id = $ial(%entry).id
var %mark = $ial(%entry).mark I presume that each lookup is stateless and an ordeal of its own. Or provide a new property "all" which stores all properties in a token string (with a suitable separator e.g. "|") in a defined order so you can do: var %ial $ial(*,%i).all
var %nick $gettok(%ial,1,$asc(|))
var %user $gettok(%ial,2,$asc(|))
var %host $gettok(%ial,3,$asc(|))
var %acct $gettok(%ial,4,$asc(|))
var %away $gettok(%ial,5,$asc(|))
var %gecos $gettok(%ial,6,$asc(|))
var %id $gettok(%ial,7,$asc(|))
var %mark $gettok(%ial,8,$asc(|))
|
|
|
|
|