Showing posts with label scan. Show all posts
Showing posts with label scan. Show all posts

Friday, 12 August 2016

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.

Monday, 27 August 2012

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.