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!

Generating random numbers (again)

A couple of years ago I wrote a post about generating random numbers.  I talked about three different ways of generating a random number (in absence of a $random function in Uniface)...

1) Use a perform to call a DLL (or shared object) that returns a random number.
2) Use $uuid to generate a random number in Uniface.
3) Use a DIY Linear Congruential Generator, built in Uniface.

I found that the perform was the best for performance, and I also stated that it gave a better randomness as well, but I failed to back this up (sorry). 

This issue has raised it's head again, as we're currently trying to get rid of all our own external libraries (DLL/SO) in order to improve maintainability and interoperability.

This time I'm going to test over 1,000,000 iterations (instead of 2,000,000 as before), as there's a little more code inside the loop to store the generated numbers.  Each method will be generating numbers between 0 and 99, and I will then plot the number of times each of these numbers is generated, and report the standard deviation as well - this should give a good idea of the spread.

1) perform: 35.98 seconds (0.036ms per value) - standard deviation: 28.870

2) $uuid: 42.8 seconds (0.048ms per value) - standard deviation: 28.869

3) DIY: 56.54 seconds (0.057ms per value) - standard deviation: 28.894

As you can see from these charts, and the standard deviation of the numbers generated, all three of these methods have a similarly decent spread.  The time difference hasn't been quite as drastic this time, although that's likely to be due to the extra code in the loop that stores the values for the spread analysis.  Unless you're planning to generate a million random numbers, it's not likely to have a noticeable effect on performance though.

One thing to note though, if you're only concerned with Windows environments, then you don't have a problem, and as long as your DLLs (or shared objects in Unix) are equivalent, then you don't have a problem.  However, the $uuid method does not work as well in Unix environments...

4) $uuid in Unix: (time is not comparable) - standard deviation: 28.833

As you can see, the spread is not uniform at all.  This is because UUID is not sufficiently random in Unix - the first 5 characters seem to be time based, then 3 random characters, then the rest remains constant within the same userver (presumably based on the machine itself and the process ID).  

Summary: As before, perform is the quickest method, but if you're supporting multiple environment configurations then it's likely that building your own random number generator (possibly using $uuid on Windows) is going to make your life much easier.

Additional: There's now a blog post about this on Uniface.info, if you're interested... http://unifaceinfo.com/random-number-generator-uniface/

What are handles and should I be using them?

The Uniface manuals describes a handle as...

A handle is a reference to an object, such as a component instance, entity, occurrence, or field. Handles can be used to call operations on the referenced object, or to pass these objects as variables and parameters.

If you're used to pointers, you may at first glance think that these are the same, but they're not.  A pointer contains the address of an item in memory and is therefore fixed, whereas a handle is an abstract reference, which means the address can be changed without breaking the reference.  This makes them very useful.

In Uniface you can have "public" or "partner" handles, which allow you to define which types of operations can access them.  They are also datatypes available for local, component and global variables, depending on the scope required.  I'm not going to discuss either of these points in detail, but I think it's handy to know.

As the description in the manual states, you can create a handle that references most Uniface objects, and there are different methods for creating these handles:  Component instances ($instancehandle), entity collections ($colhandle), entity occurrences ($occhandle), fields ($fieldhandle) and also OCX controls ($ocxhandle).  

I'm going to focus on component instances.  More specifically, I'm going to focus on creating new component instances, using newinstance and handles.  

As you might expect, creating a new instance of a form has a little lead time.  Using a handle doesn't stop this lead time, but what it does do, is mean that it only has to happen once.  This means that using a handle for a single form activation is not going to give you any advantage (unless you just love handles!) but when calling operations on the same form multiple times, handles could give you a performance improvement.

This is something like how you could activate a form...

  activate "TEST_FORM".test_oper("Test")

In fact this does an implicit newinstance as well (if it can't already find an instance with the same name as the form) and so explicitly your code could look like this...

  newinstance "TEST_FORM","TEST_FORM"

  activate "TEST_FORM".test_oper("Test")

If you were to replace this with a handle then you may use something like this...

  newinstance "TEST_FORM",theHandle

  theHandle->test_oper("Test")

Notice that in this case we have used a handle instead of an instance name in the newinstance call, and then we can use this handle in place of the activate command.  The -> is referred to by Uniface as the "dereference" operator, and is processed with a precedence of 2 (with only field indirection being higher).

So let's try these two different ways of activating an operation (in this case a very simple operation that simply returns out immediately).  The newinstance command is done before the loop, and the activate (or equivalent handle call) is done inside the loop, 200,000 times...

• Using activate: 2.56, 2.61, 2.60 (about 2.6 seconds)
• Using a handle: 2.39, 2.35, 2.39 (about 2.4 seconds)

As you can see, using a handle is marginally quicker, although you'd have to be making a lot of calls before you really noticed the difference.  

I thought that this would be even more useful when the handle references a component instance that is running on another server, such as when a form is mapped to run elsewhere, as the I thought the initial creation of the new instance would take longer here.  So I ran the same operation 20,000 times (after mapping the form)...

• Using activate: 13.39, 14.35, 12.99 (about 13.5 seconds)
• Using a handle: 13.56, 13.12, 12.91 (about 13.0 seconds)

Not much difference here either.  Having said that, maybe on a chatty network the difference would be greater.

Please note:  You must return out of the operation that you call, if you exit out then this will destroy the handle and future calls to the operation will fail with a $status of -1.  To clean up a handle you can either set it to 0 or "" (empty string). 


Summary: Handles are abstract references to pretty much any Uniface object.  They can be useful, especially if you want to call the same object multiple times, but they don't seem to have the performance benefits that I was expecting, not when it comes to component instances anyway.

Reducing your memory footprint

One common use for the while loop is to loop through a set of retrieved records.  This can also be done with a for loop, as I discussed in a previous post about types of for loops.  The example I gave was something like this...

  setocc "ent",1

  while ( $status > 0 )

    ;do something

    setocc "ent",$curocc(ent)+1

  endwhile 

This is nice and simple, and also pretty efficient.  There is one big downfall with it though, and that's memory.  In order to improve performance when you do a retrieve, Uniface works out what the "hitlist" is, but doesn't actually pull all of the retrieved records into memory.  As you loop through, more and more of the hitlist is completed, and the records are pulled into memory.  

To demonstrate this, I retrieved 600 records and then looped through them, using Process Manager to track the memory of the "uniface.exe" program...

• Initial value: 14.56Mb
• 600 records retrieved: 14.64Mb (+0.08Mb)
• Looped to occurrence 100: 14.91Mb (+0.27Mb)
• Looped to occurrence 200: 15.30Mb (+0.39Mb)
• Looped to occurrence 300: 15.70Mb (+0.40Mb)
• Looped to occurrence 400: 16.10Mb (+0.40Mb)
• Looped to occurrence 500: 16.54Mb (+0.44Mb)
• Looped to occurrence 600: 16.93Mb (+0.39Mb)

As you can see, retrieving the hitlist is just the first step, and a small one at that, the data is not read in until you loop through the occurrences.

If you had retrieved a rather large amount of data, looping through it like this would continue to hold all of that data in memory.  In the situation where you're processing records one by one, you often no longer need the record after it's been processed, so it's a good idea to discard the record, to free up the memory.  

Each time you discard a record, it removes it from the hitlist and then does an implicit setocc to the next record, which becomes the new current record.  Another thing that discard does is set $status to be the occurrence number, or 0 if there are no records left in the hitlist, just like setocc does.  This allows us to build a very similar loop to the one we had before...

  setocc "ent",1

  while ( $status > 0 )

    ;do something

    discard "ent",$curocc(ent)

  endwhile

An alternative that I often see is something more like this...

  setocc "ent",1

  while ( $hits("ent") > 0 )

    ;do something

    discard "ent",1

  endwhile

I'm not a fan of this one though, as $hits can sometimes have performance problems of it's own, caused by it's tendency to complete the hitlist in order to return the count.  

So, let's check how these different methods stack up against each other performance-wise, using the same 600 records as before...

• Original loop: 6.37, 6.02, 5.90 (around 6 seconds)
• Discard loop with $curocc: 5.95, 5.95, 5.86 (just under 6 seconds)
• Discard loop with $hits: 5.95, 6.00, 5.89 (just under 6 seconds)

As you can see, there isn't that much difference in the approaches as far as performance goes.  In this case $hits hasn't caused a problem, but if I remember correctly, it's environment and/or database specific, so that's probably why.  

Summary: Using discard with a large record set is a good idea, because it reduces the memory footprint of the userver, and at no noticeable cost to processing time.  

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.

User-defined functions

One of the things which I initially found a little odd, although very simple to grasp, was the way that Uniface allows you to create modules of code as an entry, not a function.  This entry has any number of parameters (well, there probably is a limit) which can be defined as "in", "out", or "inout".  The only thing that is returned from this entry is a numeric status, which you return and this sets $status accordingly.  I think it's fairly common that developers use a status of "0" to indicate successful and positive for additional successful status, then a negative status for errors.  Any other type of value could be returned in an "out" or "inout" parameter.


This is a very simple mechanism and it works nicely.  However, sometimes it can lead to some rather verbose code, as you have to put the call to the entry on a separate line, you can't nest the call within an if or while statement as part of the condition, for example.  Here's a simple entry which converts kilometres into miles...


  entry kms_to_mls_entr
  params
    numeric kms : in
    numeric mls : out
  endparams
    mls = kms*5/8
    return 0
  end

To convert two values using the entry and then add them, it takes 3 lines, like this...

  call kms_to_mls_entr(kms1,mls1)

  call kms_to_mls_entr(kms2,mls2)

  total = mls1 + mls2

From version 9 onwards (sorry, I can't remember the minor version number) you have another option.  It took me a while to find any information in the manuals, but it's there; they're called "User-Defined Functions".  Here's an example...

  entry kms_to_mls_func

  returns numeric

  params

    numeric kms : in

  endparams

    return kms*5/8

  end

Notice that there is a returns statement before the params, which determines what datatype should be returned.  In this case it is numeric, but it doesn't need to be.  In this case, to convert the two values using this function, it takes a single line...

  total = kms_to_mls_func(kms1) + kms_to_mls_func(kms2)

This can make the code a bit neater.  But of course I'm obsessed with performance, so my next step is the test these two methods over 2,000,000 iterations...

• entry = 00:17.74, 00:17.69, 00:17.60 (under 18 seconds)
• function = 00:13.64, 00:13.64, 0:13.67 (under 14 seconds)

So as you can see, the code is more concise and it performs better.  It also relies on less variables defined, so it's a win-win all round really.  You can even do this with a global procedure.

A bit of a side note; I thought you always had to specify a datatype when defining a parameter, and that this was always a local variable.  I discovered recently that you can also use a component variable or a painted field name, in which case you don't specify the datatype.  For example...


  entry kms_to_mls_entr
  params
    numeric kms : in
    $miles$ : out
  endparams
    $miles$ = kms*5/8
    return 0
  end

Summary: It is possible to create a "user-defined function", which is an entry that returns a specific datatype, allowing you to create more concise code, that also performs better.