Scanning is slow - should I split?

Almost 4 years ago, I wrote a post entitled Scanning is slow.  Well, to be fair, it is.

The example code that I gave was for counting how many times a substring appeared within a string...

  temp = list

  total = 0

  scan temp,"ABC"

  while ( $result > 0 )

    total = total+1

    temp = temp[$result+3]

    scan temp,"ABC"

  endwhile

I gave a perfectly simply alternative which performed much better in this scenario, using $replace and $itemcount. 

However, I found myself in a similar situation yesterday, but I couldn't use this trick, because I needed to loop through, searching for certain substrings, but without changing the string that I was looping through.

A thought occurred to me, which was that I was always taking the string from after the value I'd found and scanning again, so in this case, what about using $split instead?

To compare against to above, I came up with something like this...

  temp = list

  total = 0

  $result = $split(temp,1,"ABC",lhs,rhs)

  while ( $result > 0 )

    total = total+1

    temp = rhs

    $result = $split(temp,1,"ABC",lhs,rhs)

  endwhile

I tested this by doing 500 iterations, on a string with 500 instances (so total was 250000 at the end)...

$scan: 20.94, 20.67, 20.85 - almost 21 seconds.
$split: 27.09, 27.48, 26.83 - around 27 seconds.

So $split definitely looked worse off, it looked like $scan was better suited to what I needed (as I wasn't interested in the left hand side).

However, these tests have been seeing whether I can use $split to improve my $scan loop, and this seemed a little unfair now I'd proven it couldn't, so I thought I'd flip it on it's head and see if $scan is better at doing what $split is designed for.


So for $split this is quite easy, a simple line which splits the string into two parts...

  $result = $split(temp,1,"~",lhs,rhs)

Using $scan this is a little more complicated, and requires a little string manipulation...

  $result = $scan(temp,"~")

  lhs = temp[1:$result-1]

  rhs = temp[$result+1]

When I compared the two over 2,000,000 iterations, I got these results...

$split: 10.19, 9.78, 10.01 - around 10 seconds.
$scan: 16.60, 16.51, 16.82 - over 16 seconds.

So I've worked out that $split is good for splitting and $scan is good for scanning... Why am I writing this up in a blog post, you might wonder!

Well I then considered the fact that I was splitting a string on a delimiter that I knew existed.  And in the real world situation I was working on, this wasn't a fair assumption, as often the delimiter would not be there.  So I tried this again, but with a different delimiter, that wouldn't be found in the string...

$split: 10.66, 10.73, 10.87 - a little over 10 seconds.
$scan: 9.20, 9.00, 8.44 - around 9 seconds.

So it looks like it's not quite as straightforward as I thought.  However, the saving when it is found is quite a lot larger than the loss when it's not found, so maybe $split is still best overall.

Summary: If you're looking to scan through a string, use $scan, and if you're looking to split a string (especially if you expect the delimiter to be there), use $split.

Scanning is slow

I'm always complaining when I see people using a scan or $scan when they don't need to.  Yes, it can be very useful, sometimes it's unavoidable, but here's an example of when it should not be used.

If I asked you to count how many times a substring appeared within a string, you might think about doing it this way...

  temp = list

  total = 0

  scan temp,"ABC"

  while ( $result > 0 )

    total = total+1

    temp = temp[$result+3]

    scan temp,"ABC"

  endwhile

It's perfectly logical code, it looks through the string, scanning for the substring, counting each iteration.  I've written this code myself, a few years back, and didn't think anything of it.  I recently encountered this code that I'd written, it happens to be part of an import process I use quite often.  However, on this particular day, I was importing 10,000 records - far more than usual.  Whilst I was waiting over an hour for this to import, I decided to check the code.

I noticed that I was using a scan and thought for a moment about what alternatives there were.  The first one I thought of seemed a little strange, but I was sure it would work, so I gave it a go.  This is what it was...

  temp = $replace($replace(list,1,"·;","",-1),1,"ABC","·;",-1)

  total = $itemcount(temp)-1

As you can see, I'm first removing an list delimiters (gold-semi-colon characters) from the string, and then replacing the substring with the list delimiter instead.  This now means that I have a Uniface list, and I want to know how many of these delimiters there are in the string.  This easiest way to do this is use $itemcount to count the number of items, and then deduct one, as there's always one more item than there are delimiters.  This worked a lot quicker!

I've reproduced this for testing, using a string with 500 occurrences of the substring, and performing the count 500 times...

• scan = 00:45.01, 00:43.70, 00:44.31 (just under 45 seconds)
• list = 00:00.86, 00:00.84, 00:00.84 (under 1 second)

As you can see, quite a staggering difference.  I hope you'll think twice before using scan again!  Obviously the loop and the rebuilding of the string is contributing, but I hope this is still a convincing argument.

Summary: Scanning a string can be essential, but it's a very costly function, so it's well worth thinking about an alternative approach.

Generating random numbers

One thing that is always difficult in a system is generating a truly random number.  Computers aren't random, they're very logical, therefore this is inherently difficult.  Having said that, there's always a way to calculate a number which is "random enough".  There is no function for this in Uniface, so I'm going to look at a few different ways to achieve this.


1) perform - the only way we could find to do this originally was to build a random number function in C++ and then call out to it from our Uniface program.  Something like this...


  perform "GetRandomNumber" ;call 3gl function which returns 0-32767
  rand = $1 / 32767


2) $uuid - since the Uniface Unique Identifer function was added, this has given an alternative method.  This is largely based on the current timestamp and either includes the processor ID or the ethernet address, depending on the operating system you are using.  The value returned is a 32 character hexadecimal string, so we need to remove the non-numeric characters.  

  rand = "0.%%$replace($replace($uuid,1,'&',"",-1),1,"-","",-1)%%%" * 1

We actually found that this was not random enough on non-Windows systems, as the last part of the identifier is the same throughout each transaction, so we have used characters from 3 identifiers.


3) DIY - you could also create your own random number generator, after all, these are just mathematical formulas.  The C++ "rand" function that we utilise in method (1) is a simple Linear Congruential Generator.  This takes an initial seed value and then uses it to create the next number in the sequence, which is then used as the seed for the next number.  The key is finding a combination of values that gives an evenly distributed spread of numbers, to ensure that the numbers appear suitably random.


  $$rand = ((214013 * $$rand) + 2531011) % 4294967296
  rand = $$rand / 4294967296


As you can see, this relies on the seed value already being populated, which I've stored in a global register in this example.  This could be set in the application shell execute trigger, maybe using $uuid or a time based numeric.  


Often these algorithms return a subset of the bits in order to improve the spread, but it is not possible to do extraction at the bit level in Uniface, as far as I'm aware.  Another algorithm that is popular (and generally considered better) is a Mersenne Twister, but this uses bit-shifting techniques that I don't think are possible in Uniface either.


So let's test the performance of these different methods of 2,000,000 iterations...


1) perform = 00:10.00, 00:10.00, 00:10.01 (10 seconds)
2) $uuid = 00:32.31, 00:32.44, 00:32.39 (over 32 seconds)
3) DIY = 00:34.75, 00:34.72, 00:34.72 (under 35 seconds)


As you can see, the original perform is the quickest method (although we've found that generally using a 3GL function does not hold up very well under load and these tests are only as a single user).  It can be hard to support a 3GL function across multiple platforms, but this solution is mathematically the most random method.  Out of the alternatives, $$uuid is quite simple but does not give a good spread of random numbers, not compared with the DIY method.  


It should be emphasised that none of these methods are truly random, and therefore should not be used for cryptographic purposes.  They should be suitable for simple things though, like simulating a dice throw.


Hopefully one day Uniface will provide it's own $rand or $random function - a native function should perform the best and would hopefully be implemented in a way that was suitably random with a decent spread.


Summary: If it's feasible to use a perform then this is the best way to go, both for speed and randomness.  However, you may wish to consider building your own random number generator, possibly using a Linear Congruential algorithm.

Undocumented feature - interrupt - part eight

Continuing from part seven where we looked at "989", I will now do a full summary of the known functionality that we've looked at in this series of posts...

Code	Description	Example	Alternative
0	File information	interrupt(0,"test.txt") if ( $status < 0 )   ;file doesn't exist else   list = $result   name = $item("Name",list) ;"test"   type = $item("Type",list) ;"txt"   vers = $item("Version",list) ;""   attr = $item("Attrib",list) ;"UUU" endif	This doesn't seem to return any useful information now. Could use: $fileproperties or $lfileproperties These return lots more file information, but not the same.
2	Extract filename	interrupt(2,"C:\temp\test.txt") filename = $result ;"test.txt"	Use string manipulation (although interrupt takes 60% of the time)
3	Extract file path	interrupt(3,"C:\temp\test.txt") filename = $result ;"C:\temp\"	Use string manipulation (although interrupt takes 60% of the time)
5	Working directory	interrupt(5,"") working = $result ;"C:\temp\"	Use: $ldir
5	Uniface "usys" directory	interrupt(5,"USYS") uniface = $result ;"C:\uniface\"	Use: $fileproperties of "usys:"
6	Concatenate file path	$result = "C:\temp" interrupt(6,"test") filepath = $result ;"C:\temp\test\"	Use string manipulation (although interrupt takes 70% of the time)
7	Parent directory	interrupt(7,"C:\temp\test\") parent = $result ;"C:\temp\"	Use string manipulation (although interrupt takes 33% of the time)
10	Directory listing (files)	interrupt(10,"C:\temp") list = $result ;"test.txt·;test2.txt" count = $status ;2	Use: $dirlist or $ldirlist (with "FILE" topic)
11	Directory listing (folders)	interrupt(11,"C:\temp") list = $result ;"test·;test2" count = $status ;2	Use: $dirlist or $ldirlist (with "DIR" topic)
989	Application focus	interrupt(989,"APPLFOCUS")	No alternative (doesn't seem to work anyway)
989	Format string	$result = "RPL" interrupt(989,"FORMAT") string = $result	Use string manipulation (doesn't seem to work anyway)
989	Undo gold characters	$result = "R·;P·!L" interrupt(989,"UNDOGOLD") string = $result ;"R;P!L"	Use: $replace

It seems that the interrupt command isn't really very useful anymore.  The functionality has either been replaced by new Uniface functions, or can be achieved by string manipulation.  Given the performance improvements, it may be worth considering using interrupt if you are heavily handling file paths, but given the number of iterations needed to see the difference, I'd be surprised if this was ever worthwhile.


Given the numeric nature of the code, I'm sure that the unknowns (1, 4, 8 and 9) must do something too - I'd love to know what!  Probably some of 12-988 do something as well, so I'm sure there are some hidden gems within the interrupt command.  If you know of any, please let me know in the comments.

Undocumented feature - interrupt - part seven

Continuing from part six where we looked at "10", "11" and "12" onwards, we're now going to look at "989".  This has a number of different uses, which are used by the debugger, so should be relatively safe to use moving forwards.


989 - Application focus


When the debugger kicks in, maybe caused by a debug statement in your code, the focus is immediately set to the debugger.  Apparently this is done using the interrupt command...


interrupt(989,"APPLFOCUS")


As far as I can tell this doesn't work, maybe because I'm using Windows 7 for my testing.  When you hit a debug statement it does bring the debugger into focus, but if my Uniface application calls the interrupt command above whilst another application has focus, it does not come into focus as I would expect.





989 - Format string


According to PUUU, this is supposed to format a string by adding carriage returns in.  It's not clear on the details, but something like this...


$result = "RPL"
interrupt(989,"FORMAT")
string = $result


However, I couldn't get this to work for me, $result remained unaffected.  If you wanted to do something like this then you could use string manipulation, but I'm not sure why you'd want to.  Again, this is supposed to be used by the debugger, but I can't recall seeing an behaviour like this myself.





989 - Undo gold


When the debugger displays lists, it always uses semi-colon (;) and exclamation mark (!) as the delimiter, instead of their gold equivalents.  Apparently it uses the following command to do it...

$result = "R·;P·!L"

interrupt(989,"UNDOGOLD")

string = $result

This replaces the gold delimiters with their normal equivalents.  It does not replace the wildcard characters, only the delimiters.  This one does actually work!  It's easy to find an alternative using $replace however...

string = $replace($replace("R·;P·!L",1,"·;",";",-1),1,"·!","!",-1)

This code is probably slightly easier to read, as you can easily see which characters are included in the "undo".  How about the performance though, over 2,000,000 iterations...

• interrupt = 00:07.89, 00:07.64, 00:07.73 (almost 8 seconds)
• $replace = 00:07.95, 00:07.83, 00:07.88 (almost 8 seconds)

So as you can see, it takes pretty much exactly the same amount of time either way, so I'll definitely be sticking with the alternative, instead of using interrupt.

Summary: Numeric code "989" has multiple uses, but it seems that they either don't work any more, or are easily replaced with alternatives.  I'll do a full summary of the interrupt command in the next post.

Undocumented feature - interrupt - part five

Continuing from part four where we looked at "4", "5" and "6"...


7 - Parent directory


This sets $result to be the parent directory of the file path that you specify, like this...


  interrupt(7,"C:\temp\test\")
  parent = $result

In this case $result would be set to "C:\temp\".  You could do this with string manipulation, but you need to be careful that you check to see if the last character is a delimiter or not...

  filepath = "C:\temp\test\"

  if ( $scan(filepath,"/") < 1 ) ;calculate delimiter

    del = "\"

  else

    del = "/"

  endif

  pos = $length(filepath)

  if ( filepath[pos] = del ) ;remove last character if delimiter

    filepath = filepath[1:pos-1] 

  endif

  pos = $rscan(filepath,del) ;find last delimiter

  filepath = filepath[1,pos] ;truncate string

As you can see, this isn't very concise either, and uses $rscan as well as $scan, so it's not likely to perform very well.  As with "6", I'll test with and without the code which calculates the delimiter, over 2,000,000 iterations...

• interrupt = 00:05.16, 00:05.20, 00:05.09 (just over 5 seconds)
• alternative = 00:17.74, 00:17.52, 00:17.67 (over 17 seconds)
• without $scan = 00:15.62, 00:15.39, 00:15.41 (over 15 seconds)

Looking at these times, I'm struggling to argue for using the alternative!  I'm thinking I must be doing something wrong, so I'm going to try and refactor my alternative, without $rscan.  

I've just tried using $replace to convert the file path into a list, remove the last item (or two) and then convert it back again - this took slightly longer!  I'm going to have to give up with this for now, but I hope to tackle this again.

8 - Unknown


I haven't found any indication of what functionality this might be, but it does behave differently to "1" and "4", which are also unknown.  In this case it always returns a $status of 0 and $result is set to the string that you pass in.  I've tried all sorts of weird and wonderful things without getting anywhere, I'm giving up on this one for now too.



9 - Unknown


I haven't found any indication of what functionality this might be either.  This also behaves differently, as it always returns a $status of 0 but $result remains unaffected. 


Summary: Numeric code "7" could be very useful for finding the parent directory quickly, but "8" and "9" remain unknown.