mIRC Home    About    Download    Register    News    Help

Print Thread
$ialchan() enumeration surprisingly slow #262012
22/12/17 08:48 AM
22/12/17 08:48 AM
Joined: Feb 2003
Posts: 2,600
Raccoon Offline OP
Hoopy frood
Raccoon  Offline OP
Hoopy frood

Joined: Feb 2003
Posts: 2,600
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!
Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #262013
22/12/17 08:54 AM
22/12/17 08:54 AM
Joined: Feb 2003
Posts: 2,600
Raccoon Offline OP
Hoopy frood
Raccoon  Offline OP
Hoopy frood

Joined: Feb 2003
Posts: 2,600
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!
Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #262014
22/12/17 09:05 AM
22/12/17 09:05 AM
Joined: Feb 2003
Posts: 2,600
Raccoon Offline OP
Hoopy frood
Raccoon  Offline OP
Hoopy frood

Joined: Feb 2003
Posts: 2,600
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!
Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #262015
22/12/17 09:27 AM
22/12/17 09:27 AM
Joined: Jan 2004
Posts: 1,158
maroon Offline
Hoopy frood
maroon  Offline
Hoopy frood

Joined: Jan 2004
Posts: 1,158
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.

Code:
//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:

Quote:
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.

Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #262017
22/12/17 02:58 PM
22/12/17 02:58 PM
Joined: Dec 2002
Posts: 4,449
London, UK
Khaled Offline

Hoopy frood
Khaled  Offline

Hoopy frood

Joined: Dec 2002
Posts: 4,449
London, UK
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.

Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #262018
22/12/17 03:02 PM
22/12/17 03:02 PM
Joined: Dec 2002
Posts: 4,449
London, UK
Khaled Offline

Hoopy frood
Khaled  Offline

Hoopy frood

Joined: Dec 2002
Posts: 4,449
London, UK
Quote:
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:

Code:
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
}

Re: $ialchan() enumeration surprisingly slow [Re: Khaled] #262020
22/12/17 05:43 PM
22/12/17 05:43 PM
Joined: Apr 2004
Posts: 838
The Netherlands
Sat Offline
Hoopy frood
Sat  Offline
Hoopy frood

Joined: Apr 2004
Posts: 838
The Netherlands
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:

Code:
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.. smile


Saturn, QuakeNet staff
Re: $ialchan() enumeration surprisingly slow [Re: Sat] #262046
23/12/17 11:58 PM
23/12/17 11:58 PM
Joined: Dec 2002
Posts: 4,449
London, UK
Khaled Offline

Hoopy frood
Khaled  Offline

Hoopy frood

Joined: Dec 2002
Posts: 4,449
London, UK
Code:
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.

Re: $ialchan() enumeration surprisingly slow [Re: Khaled] #263863
01/10/18 06:44 PM
01/10/18 06:44 PM
Joined: Feb 2003
Posts: 2,600
Raccoon Offline OP
Hoopy frood
Raccoon  Offline OP
Hoopy frood

Joined: Feb 2003
Posts: 2,600
(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.

__
Code:
//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!
Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #263866
02/10/18 07:32 AM
02/10/18 07:32 AM
Joined: Dec 2002
Posts: 4,449
London, UK
Khaled Offline

Hoopy frood
Khaled  Offline

Hoopy frood

Joined: Dec 2002
Posts: 4,449
London, UK
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.

Re: $ialchan() enumeration surprisingly slow [Re: Khaled] #263869
02/10/18 04:29 PM
02/10/18 04:29 PM
Joined: Feb 2003
Posts: 2,600
Raccoon Offline OP
Hoopy frood
Raccoon  Offline OP
Hoopy frood

Joined: Feb 2003
Posts: 2,600
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.

Code:
  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!
Re: $ialchan() enumeration surprisingly slow [Re: Raccoon] #263870
02/10/18 04:39 PM
02/10/18 04:39 PM
Joined: Aug 2003
Posts: 227
UK
P
Protopia Offline
Fjord artisan
Protopia  Offline
Fjord artisan
P

Joined: Aug 2003
Posts: 227
UK
Originally Posted By: Raccoon
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.

Code:
  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:
Code:
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(|))