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.

Putlistitems - successive occurrences

I've used putlistitems a lot, it's very useful.  Different switches all it to do different things, so for example, /occ will populate a variable with an associative list of field names and values, something like this...

  putlistitems/occ varMyList,"ENT"

"varMyList" will now be something like "FIELD1=VALUE1·;FIELD2=VALUE2·;etc".

This can further be modified by adding /modonly, which will only add field values to the list which have been modified since the record was retrieved, something like this...

  putlistitems/occ/modonly varMyList,"ENT"

However, the one I tend to use most is /id.  This will take the values of the specified field from multiple occurrences and put them into a list, something like this...

  varMyList = "FIELD1"

  putlistitems/id varMyList

"varMyList" will now be something like "VALUE1·;VALUE1·;etc", repeated for each occurrence.

This allows you to quickly grab the values of the field(s) you're interested in, without having to loop through the occurrences in order to build the list, which is much better for performance.

Or you can also use it to update the representations in a list, for example, backing up a load of field or register values...

  varMyList = "$1·;$2·;$3"

  putlistitems/id varMyList

"varMyList" will now be something like "$1=REG1·;$2=REG2·;$3=REG3".

All of this is well documented in the Uniface manuals, so you may well be asking me why I'm telling you this.  Fair question.

I never realised that the first use of /id, taking the values of the specified field from multiple occurrences, was actually successive occurrence.  This means that it will start on the current occurrence and loop through to the end, completing the hitlist if required.

The manuals make this clear, with the following note...

To ensure that the entire set of occurrences in the component is being addressed, make the first occurrence the current occurrence.

What this means is, use setocc first, like this..

  setocc "ENT",1

  varMyList = "FIELD1"

  putlistitems/id varMyList

I hope I've not been caught out by this in the past!

Summary: putlistitems/id will look at successive occurrences, so if you want the whole hitlist, remember to make sure the current occurrence is the first occurrence.

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!

Undocumented feature - assignment files

I was asked yesterday if I knew about the Uniface function $assignments.  I did and it's something that we started using as soon as it became available (from version 9.something) and it's incredibly useful.  I searched the manuals so that I could send the enquirer the details, but I couldn't find any reference to it.

When a userver starts up, it reads the assignment file in order to get numerous settings.  There are many sections, including a custom section called "logicals", which allows you to add your own assignment files settings, which can be read using the $logical function.  

It is now possible to list all of the logicals at once, like this...

  list = $assignments("LOGICALS")

This returns a Uniface list of all the logicals.  It is possible to return any section of the assignment files in this way, including "paths", "files" and "services_exec".

This was mentioned on the Hacking UnifAce blog over a year ago, but hopefully you find it useful.

Summary: You can access the assignment file settings in code, listed by their section, which can be useful for checking which settings the current userver is using.

Variables as lists

I think you'd be hard pushed to find a Uniface developer that didn't know that a string variable can be used to hold a list of values.  The Uniface list construct uses a gold-semi-colon as the list delimiter, denoted in the manuals as ; but in code looks like ·; - for example...

  s = "27/Sep/2012·;28/Sep/2012·;29/Sep/2012"
      ;27/Sep/2012·;28/Sep/2012·;29/Sep/2012

I spent quite a long time today trying to work out why such a simple thing was not working for me.  It took quite a long time for me to realise that I'd accidentally declared (or rather, re-used) a numeric variable.  This gives a rather different result...

  n = "27/Sep/2012·;28/Sep/2012·;29/Sep/2012"

      ;27·;28·;29

I wasn't previous aware that a numeric variable could hold a list in this way, but it's handy to know! 

The same also works with dates...

  d = "27/Sep/2012·;28/Sep/2012·;29/Sep/2012"

      ;2012092700000000·;2012092800000000·;2012092900000000

Take a look at this screenshot to see the results...

I'm not going to go through all the data types to confirm which ones it works with, but I suspect it would work with all of the simple ones (such as datetime and float) but not with the more complex ones (such as handle and occurrence).

Summary: It's not just string variables that can be used to hold lists; numeric and date variables also can, along with many others I suspect.

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.

Types of for loops - part one

I have already discussed the basic for loop in my last post, but in Uniface 9.5 there were a number of other list constructs made available, which I plan to investigate over the next few posts, having never used them before.  


I wrote a post a couple of months ago entitled Performance of list processing, which looked at different ways of looping through a Uniface list of values.  In this post I determined that one of the quickest ways was a while loop with a counter, using getitem to extract each value in turn, something like this...


  count = 0

  $status = 1

  while ( $status > 0 )

    count = count+1

    getitem temp,list,count

    ;do something

  endwhile

However, one of the new constructs is forlist, which can be used to the same affect...

  forlist temp,count in list

    ;do something

  endfor

As you can see, the code is much more concise.  There is no need to initialise the count variable or  $status, everything is done as part of the forlist statement, and the incrementing and extracting are done automatically.  The "count" variable is optional, if you don't need it then you don't need to include it.

It is also possible to do the same thing when you have an ID list, where the same construct will return both the ID and the value of each item in the list separately...


  forlist/id id,temp,count in list

    ;do something

  endfor

The "count" variable is also optional in this case.  You know what's coming next...

So let's test these three blocks of code over 2,000,000 iterations...

• while = 01:18.47, 01:17.55, 01:18.11 (around 1 minute 18 seconds)
• forlist = 01:08.06, 01:08.51, 01:08.42 (just over 1 minute 8 seconds)
• forlist/id = 01:17.27, 01:18.03, 01:17.26 (just over 1 minute 17 seconds)

As you can see, forlist is not only more concise from a coding perspective, but it also performs better.  Given the number of iterations, the performance gain would probably be limited, but it is clearly the better option.

Summary: Whilst I have previously always used while loops, I shall now be considering switching the forlist loops, for iterating through a list.  

Performance of list processing

As mentioned in my previous posts, performance is a key factor.  The lovely Uniface list is effectively string a delimited string, as you know, which means we're back to string manipulation, which we know is costly.  Unfortunately there are no arrays or similar available, so we make do.


As far as I can see, there are four ways to process a list....

1. getitem with a counter
   
   
   count = 0
   $status = 1
   while ( $status > 0 )
     count = count+1
     getitem temp,list,count
   endwhile
   
   
2. getitem/id with a counter
   
   
   count = 0
   $status = 1
   while ( $status > 0 )
     count = count+1
     getitem/id temp,list,count
   endwhile
   
   
3. getitem with a destructive list
   
   
   count = 0
   while ( list != "" )
     count = count+1
     getitem temp,list,1 
     delitem list,1
   endwhile
   
   
4. getitem with a reverse destructive list 
   
   
   count = 0
   while ( list != "" )
     count = count+1
     getitem temp,list,-1
     delitem list,-1
   endwhile

These loops all use local variables and the list is pre-built with 20,000 items like...

"1= ABCDEFGHIJKLMNOPQRSTUVWXYZ 01234567890 abcdefghijklmnopqrstuvwxyz 01234567890"

1. 00:06.58, 00:06.54, 00:06.69 (just under 7 seconds)
2. 00:06.85, 00:06.89, 00:06.84 (just under 7 seconds)
3. 01:02.16, 01:01.87, 01:01.91 (just over 1 minute)
4. 00:06.61, 00:06.63, 00:06.72 (just under 7 seconds)

There is obviously a clear loser here, never do a destructive list!  I think the main reason for this is that the getitem must have to scan through the string, but the delitem is then causing the whole list to be rebuilt - very costly!  

Now I shall try again but with a pre-built list of 200,000 items, the same as those before...

1. 01:06.55, 01:06.38, 01:05.99 (just over 1 minute)
2. 01:19.22, 01:19.88, 01:19.36 (around 1.3 minutes)
3. -
4. 01:05.38, 01:06.59, 01:05.45 (just over 1 minute)

This shows that the next worst is the getitem/id, whereas the remaining two are pretty close.  The reason I think the reverse destructive list works fairly well is that the list is being shortened each time, which means there is a smaller string to scan.  However, finding the first item must be quicker than finding the last, implying that the scan always happens from the first character.  What this probably means, although the numbers are too close to really prove this, is that the reverse destructive starts to perform better for really really long lists, but the plain getitem performs just as well for shorter lists.

Summary: When processing a list it is best to use either a getitem with a counter or a reverse destructive list, as these both perform well for normal sized lists.