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.

Performance of getitem

I've previously posted about how scanning is slow, and I stand by that.  But I've recently discovered that in some situations, it can be less slow than using getitem.  

I was doing a code review of some old code and found that it was using $scan in a situation where I thought you'd usually use getitem, and wondered why someone would have done it this way.  But before I replaced it, I wanted to check the performance to see what difference I would be making by changing it, and I was surprised by the results!

The code was designed to check if a variable matched one of a reasonably large number of items.  For this example, if stuck with 10 items...

  if ( temp = "ONE" | temp = "TWO" | temp = "THREE" | temp = "FOUR" | temp = "FIVE" | temp = "SIX" | temp = "SEVEN" | temp = "EIGHT" | temp = "NINE" | temp = "TEN" )

    ;testing condition

  endif

I could have used a line continuation marker, but you get the idea.

What the developer had done is replaced this set of conditions with a single $scan, like this...

  list = "|ONE|TWO|THREE|FOUR|FIVE|SIX|SEVEN|EIGHT|NINE|TEN|"
  if ( $scan(list,"|%%temp%%%|") > 0 )

    ;testing condition

  endif

Note that this is not a Uniface list, a "bar" or "pipe" character has been used as the delimiter - this is placed at the beginning and end of the value to ensure it is not found as a sub-part of another longer value.  It This takes up a lot less space, and is perfectly readable, but I was concerned about performance.  

To test this, I wanted to make sure it was fair, so I decided to always check both the first and the last item in the list in each iteration.  I also wanted to test in a few different ways, and I came up with 4...

1) Set of conditions

  temp = "ONE"

  if ( temp = "ONE" | temp = "TWO" | temp = "THREE" | temp = "FOUR" | temp = "FIVE" | temp = "SIX" | temp = "SEVEN" | temp = "EIGHT" | temp = "NINE" | temp = "TEN" )

    ;testing condition

  endif

  temp = "TEN"

  if ( temp = "ONE" | temp = "TWO" | temp = "THREE" | temp = "FOUR" | temp = "FIVE" | temp = "SIX" | temp = "SEVEN" | temp = "EIGHT" | temp = "NINE" | temp = "TEN" )

    ;testing condition

  endif

2) $scan a bar delimited string

  list = "|ONE|TWO|THREE|FOUR|FIVE|SIX|SEVEN|EIGHT|NINE|TEN|"
  if ( $scan(list,"|ONE|") > 0 )

    ;testing condition

  endif
  list = "|ONE|TWO|THREE|FOUR|FIVE|SIX|SEVEN|EIGHT|NINE|TEN|"

  if ( $scan(list,"|TEN|") > 0 )

    ;testing condition

  endif

3) getitem/id a Uniface list

  list = "ONE·;TWO·;THREE·;FOUR·;FIVE·;SIX·;SEVEN·;EIGHT·;NINE·;TEN"

  getitem/id temp,list,"ONE"

  if ( $status > 0 )

    ;testing condition

  endif

  list = "ONE·;TWO·;THREE·;FOUR·;FIVE·;SIX·;SEVEN·;EIGHT·;NINE·;TEN"

  getitem/id temp,list,"TEN"

  if ( $status > 0 )

    ;testing condition

  endif

4) $item a Uniface list

  list = "ONE·;TWO·;THREE·;FOUR·;FIVE·;SIX·;SEVEN·;EIGHT·;NINE·;TEN"

  if ( $item("ONE",list) != "" )

    ;testing condition

  endif

  list = "ONE·;TWO·;THREE·;FOUR·;FIVE·;SIX·;SEVEN·;EIGHT·;NINE·;TEN"

  if ( $item("TEN",list) != "" )

    ;testing condition

  endif

I wasn't really sure what I was expecting, but I thought the $scan would be the worst performance.  I tested over 2,000,000 iterations, and here's what I got...

1) Set of conditions: 37.30, 36.95, 37.83 = 37.36 secs
2) $scan a bar delimited string: 21.76, 21.97, 21.24 = 21.66 secs
3) getitem/id a Uniface list: 24.46, 24.22, 24.89 = 24.52 secs
4) $item a Uniface list: 22.65, 23.25, 23.47 = 23.12 secs

So the slowest was the set of conditions.  I didn't test it, but knowing that if statements shortcut I figure that if the item was always passing the first condition it would be quick, but because half of my test items were only passing the last condition, it would have to check each of the conditions in the set before it passed.

Although there wasn't a big difference, what surprised me is that the getitem/id and $item were actually slower than the $scan in this case.  I then remembered back to a conversation on the Uniface-L mailing list, which talked about how Uniface handles lists in the background.  The description there indicates that an array is built in the background, which means there is an upfront cost for calling getitem/id (or $item) once, but then if you're looping through it is much quicker to access the rest, because the array can be used.  However, because I'm rebuilding the list each time, that means the array needs to be rebuilt each time.  

This means that actually $scan can be used to improve the performance when checking that an item is in a list, as long as you're only checking this list once and it's not going to be re-used.  I expect there to be a point at which the number of times the list is re-used means that using getitem/id (or $item) would become better for performance.

Also, I've not tested different lengths of lists.  However, given the results and my reasoning for why the results ended up this way, I would have thought extending the list would simply emphasize the results.

Summary:  Checking if an item is in a list can be done a number of ways, and if it's being done a lot of times, performance can be eeked out by using a $scan, surprisingly!

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.

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.

Undocumented feature - interrupt - part four

Continuing from part three where we looked at "2" and "3"...


4 - Unknown


I haven't found any indication of what functionality this might be, but it does behave differently to "1", which was also unknown.  In this case it always returns a $status of 0 and $result is a blank string.  I tried folders, subfolders, filenames and a blank string, with no difference in behaviour.  I'm giving up, for now.



5 - Working directory


As discussed in part one, using numeric code "5" returns the working directory...

  interrupt(5,"")
  working = $result

The alternative is to use $ldir...

  working = $ldir()

The alternative is more maintainable, safer and also performs better.

6 - Concatenate file path

This takes the file path which is currently in $result and then concatenates the path you pass in, automatically adding the folder delimiters where necessary.  Here's some example code...

  filepath = "C:\temp"

  $result = filepath

  interrupt(6,"test")

  filepath = $result

This will then populate $result with "C:\temp\test\".  As you can see, I had excluded the delimiter from the end of both the original $result value and the value I passed it, but the interrupt command fixed that.  Again, this is another string manipulation example, I came up with something like this...

  filepath = "C:\temp" 

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

    del = "\"

  else

    del = "/"

  endif

  pos = $length(filepath)

  if ( filepath[pos] != del ) ;check filepath ends with delimiter

    filepath = "%%filepath%%del%%%"

  endif

  filepath = "%%filepath%%%test%%del%%%" ;concatenate filepath

As you can see, this isn't very concise, primarily because I'm accounting for Windows and Unix environments again, meaning that I have to first calculate the "del" local variable.  You could of course use $concat instead of using substitution, like I have.


I tested these two methods over 2,000,000 iterations with the following results...

• interrupt = 00:06.67, 00:06.75, 00:06.72 (almost 7 seconds)
• alternative = 00:12.02, 00:12.00, 00:12.04 (about 12 seconds)
• without $scan = 00:09.04, 00:09.78, 00:09.74 (almost 10 seconds)

I added a third option which was the alternative but with a hardcoded delimiter instead of calculating it, so the performance can be improved by having a global register that holds this.  Still, in this case the interrupt command is better for performance and is less lines of code.  

Summary: Numeric code "4" remains unknown for now, "5" has been replaced by a better alternative and "6" seems to still be useful, although I think I'd still opt for string manipulation which I know that I can control over an undocumented feature.

Validating a numeric string

Today I wanted to validate a numeric string, in the format "YYYYMMDD".  I wasn't particularly worried about checking that there were only 12 months in the year, 28-31 days in the month, or whether the year was in a sensible range, I just wanted to make sure that I'd found a string of 8 numeric digits.


So my first thought was to check the length using $length, an easy place to start...

  if ( $length(str) = 8 )

    ;good start

  endif

Next I went on to think about checking it was numeric, $number being the first function that popped into my head which seemed relevant...

  if ( $length(str) = 8 & $number(str) = str )

    ;pretty good

  endif

But then I remember that this matches even if the string contains spaces, which I didn't want (nor do I think is correct, personally), so I had to add a check for that...

  if ( $length(str) = 8 & $number(str) = str & $scan(str," ") = 0 )

    ;even better

  endif

And then I thought about other "numeric" characters that were allowed.  Depending on your language settings, this could include plus (+), minus (-), fullstop (.) and comma (,) - there may be more as well. 


It was at this point that I thought I must be doing something wrong, this clearly wasn't the best way of doing this.  


Then I remember a suggestion a colleague of mine had made to me when I started this blog - syntax strings.  It's very easy to use a syntax string to pattern match for numbers...

  if ( $length(str) = 8 & str = '#*' )

    ;much better

  endif

I won't go into the details of syntax strings as this is well documented, but suffice to say that a hash (#) means a numeric digit (0-9) and star (*) means any number of them (0-n).  Combined with my length check, this seemed right.  

But then it occurred to me that I could improve this even further...

 if ( str = '########' )

    ;perfect

  endif

In this case I have specified that I require 8 numeric digits, which is exactly what I wanted to check for.  Obviously using a syntax string here has simplified my code and made it much more readable, it's clear to another developer what I'm trying to achieve.

Now usually I'd have settled for the code that was using $length, $number$ and $scan, which would have sufficed and seemed pretty logical as I was writing it.  But noticing how much more elegant this code was got me thinking... How much better does this code perform?  Surely better than all those function calls!

I took the last 3 of my code blocks and ran them 2,000,000 times, giving the following results...

• $length+$number+$scan = 00:07.70, 00:07.70, 00:07.65 (almost 8 seconds)
• $length+syntax string = 00:06.33, 00:06.25, 00:06.27 (over 6 seconds)
• Just the syntax string = 00:05.00, 00:05.09, 00:05.00 (about 5 seconds)

As you can see not only is this code more elegant and therefore more maintainable, but it also performs better.  Given then difference is only a second or two over 2 million iterations, it's not really much of a consideration by itself, but they say every little helps!

Thanks to Dave W for the inspiration which led to this post.

Summary: Don't always jump to using Uniface functions for validation and other checks, it can often be simpler and more efficient to use syntax strings to perform pattern matches.