Finding Records

In the last blog post, I found out that  one can load pretty quickly several thousand or even tens of thousands records to memeory. This time I would like to examine how quickly you can find records within such a list.

Autocomplete

As a use case, I have a picklist with auto-completion in mind. The user enters separately (partial) words separated by spaces. He receives a list with possible matches after each key down.

Function: Query
    Returns
        listBlz: cBlz
    Parameters
        String: sQuery
        Number: nMaxResult
    Local variables
        String: asQueryParts[*]
        Number: nCountQueryParts
        Number: nListIdx
        Number: nQueryPartIdx
        listBlz: listBlzResult
        Boolean: bNotFound
    Actions
        ! Clean Query
        Call SalStrTrim( sQuery, sQuery )
        ! Tokenize Query-String to single words
        Set nCountQueryParts = SalStrTokenize( sQuery, '', ' ', asQueryParts )
        If ( nCountQueryParts = 0 )
            ! return empty list
            Return listBlzResult
        ! Validate / normalize parameters
        If (nMaxResult <= 0 )
            ! default to max 10 hits
            Set nMaxResult = 10
        ! Query all interesting Fields of our list
        While (nListIdx < __nLength )
            Set bNotFound = FALSE
            Set nQueryPartIdx = 0
            While ( nQueryPartIdx < nCountQueryParts )
                ! check if QueryPart can be found in one of the fields
                ! SalStrScan ist case insensitive - so there is no need for lower or upper strings
                If (
                            (SalStrScan(__acBlz[nListIdx].sBezeichnung, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sOrt, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sKurzbezeichnung, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sBlz, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sBic, asQueryParts[nQueryPartIdx]) = -1)
                        )
                    Set bNotFound = TRUE
                    ! Querypart could not be found so current item does not match -> break inner while
                    Break
                Set nQueryPartIdx = nQueryPartIdx + 1
            ! Add item to list if every querypart matched
            If ( NOT bNotFound )
                Call listBlzResult.Add( __acBlz[nListIdx] )
                ! break outer while if we have enough items in the resulting list
                If ( listBlzResult.Length() >= nMaxResult )
                    Break
            Set nListIdx = nListIdx + 1
        Return listBlzResult

Performance analysis

To measure the performance of the method shown above, I’ve prepared 1,000 queries. These contain up to three words of different length again randomly selected from the list of data. The search can be quickly finished if only one letter is specified. Then the hit list is most likely filled after a few queried list entries and the search can be cancelled. However, given many words it can happen that the complete list must be queried before the search inevitably finishes. I will evaluate the times for each of the 1,000 queries and show them as a histogram. Most interesting are the average and maximum search time. Both could affect the „user experience“ (UX). The performance analysis will be made with a list of 4,000 entries and another one with 20,000 entries. The measurement was carried out on a standard desktop computer.

Result

With a list size of 4,000 items the average time per query is 0.03 seconds and the longest search lasted not more than 0.1 seconds. Even with 20,000 items the search speed is still very neat taking about 0.1 seconds on average. But it may take up to half a second in the worst case.

TimePerQuery

Conclusion

The full-text search within 20,000 records in memory is pretty fast even with a simple implementation. In the next blog post I will show an autocomplete picklist based on the query function above.

Datensätze finden

Im letzten Blogpost habe ich festgestellt, dass man einige tausend oder auch zigtausend Datensätze recht schnell in den Speicher laden kann. Dieses Mal möchte untersuchen, wie schnell man innerhalb einer solchen Liste Datensätze finden kann.

Autocomplete

Als Anwendungsfall habe ich eine Suche mit Autovervollständigung im Auge: Der User gibt einzelne (Teil-)wörter mit Leerzeichen getrennt ein. Er bekommt nach jedem Tastendruck eine Vorschlagsliste mit möglichen Treffern angezeigt.

Die Listenklasse aus dem letzten Blog wird dazu um die Funktion „Query“ erweitert. Diese Funktion erwartet einen Suchstring z.B. „spark hanno“. Sie sucht innerhalb der Liste nach Datensätzen, die alle Teilwörter enthalten. Ist eine vorgegebene Anzahl an Treffern erreicht oder die Liste bis zum Ende durchsucht, bricht die Suche ab und gibt die Trefferliste zurück.

Function: Query
    Returns
        listBlz: cBlz
    Parameters
        String: sQuery
        Number: nMaxResult
    Local variables
        String: asQueryParts[*]
        Number: nCountQueryParts
        Number: nListIdx
        Number: nQueryPartIdx
        listBlz: listBlzResult
        Boolean: bNotFound
    Actions
        ! Clean Query
        Call SalStrTrim( sQuery, sQuery )
        ! Tokenize Query-String to single words
        Set nCountQueryParts = SalStrTokenize( sQuery, '', ' ', asQueryParts )
        If ( nCountQueryParts = 0 )
            ! return empty list
            Return listBlzResult
        ! Validate / normalize parameters
        If (nMaxResult <= 0 )
            ! default to max 10 hits
            Set nMaxResult = 10
        ! Query all interesting Fields of our list
        While (nListIdx < __nLength )
            Set bNotFound = FALSE
            Set nQueryPartIdx = 0
            While ( nQueryPartIdx < nCountQueryParts )
                ! check if QueryPart can be found in one of the fields
                ! SalStrScan ist case insensitive - so there is no need for lower or upper strings
                If (
                            (SalStrScan(__acBlz[nListIdx].sBezeichnung, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sOrt, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sKurzbezeichnung, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sBlz, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sBic, asQueryParts[nQueryPartIdx]) = -1)
                        )
                    Set bNotFound = TRUE
                    ! Querypart could not be found so current item does not match -> break inner while
                    Break
                Set nQueryPartIdx = nQueryPartIdx + 1
            ! Add item to list if every querypart matched
            If ( NOT bNotFound )
                Call listBlzResult.Add( __acBlz[nListIdx] )
                ! break outer while if we have enough items in the resulting list
                If ( listBlzResult.Length() >= nMaxResult )
                    Break
            Set nListIdx = nListIdx + 1
        Return listBlzResult

Performanceanalyse

Um die Leistungsfähigkeit der oben gezeigten Funktion zu messen, habe ich zunächst 1.000 Queries vorbereitet. Diese enthält jeweils ein bis drei Teilwörter verschiedener Länge, die wiederum zufällig aus der Liste der Daten ausgewählt werden. Die Suche kann sehr schnell beendet sein wenn z.B. nur ein Buchstabe angegeben wurde, dann ist die Trefferliste höchstwahrscheinlich nach wenigen untersuchten Listeneinträgen gefüllt und die Suche kann abgebrochen werden. Hat man hingegen viele Teilwörter angegeben kann es vorkommen, dass die komplette Liste durchsucht werden muss, bis die Suche zwangsläufig abgebrochen werden kann. Ausgewertet werden die Zeiten für jeden der 1.000 Beispielquerys und als Histogramm aufgetragen. Interessant sind die mittlere und die maximale Suchzeit. Beides dürfte sich auf die „User Experience“ (UX) auswirken. Einmal wurde die Suche in einer Liste mit etwas über 4.000 Einträgen vorgenommen, ein zweites Mal war die Liste knapp 20.000 Einträge lang. Ausgeführt wurden die Messungen auf einem handelsüblichen Desktoprechner.

Ergebnis

Bei einer Listengröße von 4.000 Elementen liegt die durchschnittliche Zeit pro Query bei 0,03 Sekunden und die längste Suche dauerte nicht länger als 0,1 Sekunden. Auch bei 20.000 Elementen ist die Suchgeschwindigkeit immer noch sehr ordentlichen mit 0,1 Sekunden. Sie kann aber auch bis zu einer halben Sekunde dauern.

TimePerQuery

Fazit

Die Volltextsuche innerhalb von 20.000 Datensätzen im Speicher ist selbst mit einer einfachen Implementierung performant. Damit steht der Entwicklung einer Autocomplete-Picklist nichts mehr im Weg. Diese möchte ich im nächsten Blogpost vorstellen.

Loading Data to Memory: A Performance Analysis

 
Loading Rows in Memory

Recently I wanted to find out how long it takes to fetch thousands of records in memory.

So first I created a functional class as a struct in which instance variables the values are loaded. A struct is equivalent to a row of data. An instance variable is equivalent to a column. Here is an example data structure of the bank codes file of the Deutsche Bundesbank:
Functional Class: structBlz
  Instance Variables
   String: sBlz
   Number: nMerkmal
   String: sBezeichnung
   String: sPlz
   String: sOrt
   String: sKurzbezeichnung
   Number: nPan
   String: sBic
   String: sPrüfzifferBerechnung
   String: sDatensatzNummer
   String: sÄnderungskennzeichen
   Boolean: bBankleitzahlLöschung
   String: sNachfolgeBankleitzahl
The rows of data were loaded into another functional class called listBlz and stored in the memory as a dynamic array. The list class has two methods: Add(structBlz) adds a data row in the dynamic array. The Load() method loads the tab separated bank code file that contains nearly 20,000 rows.
Functional Class: listBlz
  Instance Variables
    structBlz: __acBlz[*]
    Number: __nLength
  Functions
    Function: Add
      Returns Boolean:
      Parameters
        structBlz: cBlz
      Actions
        Set __acBlz[__nLength] = cBlz
        Set __nLength = __nLength + 1
    Function: Load
      Returns Boolean:
      Parameters
        String: sPathFile
      Local variables
        File Handle: hFile
        String: sLine
        structBlz: cBlz
        String: asTokens[*]
      Actions
        Call SalStrSetBufferLength( sLine, 1024 )
        If ( SalFileOpen( hFile, sPathFile, OF_Read ) )
          While ( SalFileGetStr( hFile, sLine, 1024 ) )
            SalStrTokenize( sLine, '', ' ', asTokens )
            Set cBlz = new structBlz
            Set cBlz.sBlz = asTokens[0]
            Set cBlz.nMerkmal = SalStrToNumber(asTokens[1])
            Set cBlz.sBezeichnung = asTokens[2]
            Set cBlz.sPlz = asTokens[3]
            Set cBlz.sOrt = asTokens[4]
            Set cBlz.sKurzbezeichnung = asTokens[5]
            Set cBlz.nPan = SalStrToNumber( asTokens[6] )
            Set cBlz.sBic = asTokens[7]
            Set cBlz.sPrüfzifferBerechnung = asTokens[8]
            Set cBlz.sDatensatzNummer = asTokens[9]
            Set cBlz.sÄnderungskennzeichen = asTokens[10]
            Set cBlz.bBankleitzahlLöschung = SalStrToNumber( asTokens[11] )
            Set cBlz.sNachfolgeBankleitzahl = asTokens[12]
            Call Add(cBlz)
          Call SalFileClose( hFile )
Loading of around  20,000 records in the memory takes less than a second. To eliminate the effect of the tokenizer I stored the entire row of data in just on property cBlz.sBlz, which you arrive at 0.4 seconds. So most of the time is due to the use of SalStrTokenize. It would probably be better to use a fixed field length data format.

Loading Rows in Memory

Loading data from a database, you get a similar performance. You can fetch approximately 20,000 records (with approximately 10-15 columns) in a half-second. This is much faster than to load data into a ChildTable. This gives us interesting possiblilities which I want to show you in the next blog.

Datensätze laden: Performance-Analyse

 
Loading Rows in Memory

Neulich wollte ich herausfinden, wie lange es dauert, tausende von Datensätzen in den Speicher zu laden und dort vorzuhalten.

Dazu habe ich zunächst eine funktionelle Klasse als Struct erstellt, in deren Instanzvariablen die Werte geladen werden. Ein Struct entspricht also einer Datenzeile, eine Instanzvariable einer Datenspalte. Hier ein Beispiel um die Bankleitzahlen-Datei der Deutschen Bundesbank einzulesen:

Functional Class: structBlz
  Instance Variables
   String: sBlz
   Number: nMerkmal
   String: sBezeichnung
   String: sPlz
   String: sOrt
   String: sKurzbezeichnung
   Number: nPan
   String: sBic
   String: sPrüfzifferBerechnung
   String: sDatensatzNummer
   String: sÄnderungskennzeichen
   Boolean: bBankleitzahlLöschung
   String: sNachfolgeBankleitzahl

Die Datenzeilen wurden in einer weiteren funktionellen Klasse  namens listBlz geladen und im Speicher als dynamisches Array abgelegt. Die Listklasse enthält zwei Methoden: Add(structBlz) fügt eine Datenzeile im dynamischen Array an. Load() lädt die Tab getrennt Bankleitzahlendatei, die knapp 20.000 Datenzeilen enthält.

Functional Class: listBlz
  Instance Variables
    structBlz: __acBlz[*]
    Number: __nLength
  Functions
    Function: Add
      Returns Boolean:
      Parameters
        structBlz: cBlz
      Actions
        Set __acBlz[__nLength] = cBlz
        Set __nLength = __nLength + 1
    Function: Load
      Returns Boolean:
      Parameters
        String: sPathFile
      Local variables
        File Handle: hFile
        String: sLine
        structBlz: cBlz
        String: asTokens[*]
      Actions
        Call SalStrSetBufferLength( sLine, 1024 )
        If ( SalFileOpen( hFile, sPathFile, OF_Read ) )
          While ( SalFileGetStr( hFile, sLine, 1024 ) )
            SalStrTokenize( sLine, '', ' ', asTokens )
            Set cBlz = new structBlz
            Set cBlz.sBlz = asTokens[0]
            Set cBlz.nMerkmal = SalStrToNumber(asTokens[1])
            Set cBlz.sBezeichnung = asTokens[2]
            Set cBlz.sPlz = asTokens[3]
            Set cBlz.sOrt = asTokens[4]
            Set cBlz.sKurzbezeichnung = asTokens[5]
            Set cBlz.nPan = SalStrToNumber( asTokens[6] )
            Set cBlz.sBic = asTokens[7]
            Set cBlz.sPrüfzifferBerechnung = asTokens[8]
            Set cBlz.sDatensatzNummer = asTokens[9]
            Set cBlz.sÄnderungskennzeichen = asTokens[10]
            Set cBlz.bBankleitzahlLöschung = SalStrToNumber( asTokens[11] )
            Set cBlz.sNachfolgeBankleitzahl = asTokens[12]
            Call Add(cBlz)
          Call SalFileClose( hFile )

Das Laden der knapp 20.000 tausend Datensätze in den Speicher dauert erwas weniger als eine Sekunde. Probehalber habe ich auf Tokenize verzichtet und die gesamte Datenzeile in cBlz.sBlz gespeichert, womit man bei 0,4 Sekunden landet. Die meiste Zeit geht hier also für SalStrTokenize drauf.  Vermutlich wäre es also besser, ein Datenformat mit fester Feldlänge zu verwenden.

Loading Rows in Memory

Lädt man Daten aus einer Datenbank, kommt man auf eine ähnliche Performance. Man kann in etwa 20.000 Datensätze (mit etwa 10-15 Spalten) in einer halben Sekunde in den Speicher laden. Das ist viel schneller, als Daten in eine ChildTable zu laden. Das eröffnet uns interessante Möglichkeiten, die ich im nächsten Blog aufzeigen möchte.

Building Really Long Strings

Dynamically building strings with Gupta is actually pretty fast – at least if the resulting string is below 1,000,000 characters long. The need for the composition of strings beyond 32kByte is also low: SQL statements are usually limited to 32 KB length, otherwise the input buffer is complaining. The multiline text box is limited to this length also. Row-oriented file exports consist rarely of extremely long rows of data.

Concatenate can take some time

But, when serializing data in XML or JSON format, it can happen that one has to build very long strings of about 1-10 MB of characters when you cant write parts to disk inbetween. What you do ist to concatenate short stringparts to a large output string  (for example, an XML tag with content and end tag). From a certain length on the time required to append additional strings is getting extreme. Building a string with up to 500,000 characters takes about two seconds on an average desktop computer. A million characters take up to 40 seconds. For ten million characters, I had no more patience. That had to be optimized. Because in itself, Gupta has no problem with very large strings: one can read files with tens of megabytes in size with SalFileRead(…) as a BLOB. But frequently concatenating short strings can become very time consuming.

Analysis

For a quantitative analysis I have written a small program. In a loop I append short strings of length 10 to sOut. Once per 100 passes the time is measured and exported to a CSV file. The result is plotted in the following diagram:

StringAppend Time Length Diagram

You can see a sharp bend at stringlength 500,000 characters from which on adding further stringparts takes much longer (in debug mode the bend is located at 100,000 characters).

Accelerator

Adding stringparts to a temporary string which will be concatenated to the output string when it reaches a length of N characters,  you can speed up the process as a whole. I have determined the optimal value for N through a series of tests. It lies between 10,000 and 20,000 as can be seen in the following graphic. To create a 10 MByte string from a total of one million string attachments takes only 13 seconds.
StringBuilder Performance Run

StringBuilder Performance Run

StringBuilder

I packed the behavior described above in a class StringBuilder with the following methods: Append(…) appends a stringpart, ToString() returns the output string. Lenght() returns the current length of the output string  and clear() resets it. You can download the source code of StringBuilder including the performance tests.

Download

StringBuilderPerfomanceTests.zip

Happy coding

Echt lange Strings bauen

Das dynamische Erzeugen von Strings um z.B. SQL-Statements oder Zeilen für Datenexporte zu bauen geht mit Gupta eigentlich recht flott – zumindest wenn die resultierenden Strings weit unter 1.000.000 Zeichen lang sind. Der Bedarf für dynamisch zusammengesetzte Strings jenseits der 32kByte-Grenze ist ja auch gering: SQL-Statements sind i.d.R. auf 32 kByte Länge begrenzt, da sonst der Input-Buffer meckert. Die Multiline-Textbox ist auf diese Länge begrenzt. Bei zeilenorientierten Exporten hat man selten mit extrem langen Datenzeilen zu tun.

Konkatenieren kann dauern

Beim Serialisieren von Daten z.B. im XML- oder JSON-Format kann es aber vorkommen, dass man sehr lange Strings mit über 1-10 MByte erzeugen muss, ohne sie zwischendurch auf die Festplatte wegschreiben zu können. Dabei wird jeweils ein kurzer String (z.B. ein XML-Tag mit Inhalt und Abschlusstag) an den Output-String angehängt. Ab einer bestimmten Länge wird der Zeitbedarf jedoch extrem. Bis zur Größe von 500.000 Zeichen dauert das auf einem normalen Desktop-Rechner etwa zwei Sekunden. Eine Million Zeichen dauern schon bis zu 40 Sekunden. Bei zehn Millionen Zeichen hatte ich keine Geduld mehr. Das musste optimiert werden. Denn an sich hat Gupta kein Problem mit sehr großen Strings: Files mit einer Größe von zig Megabyte kann man mit SalFileRead(…) ohne weiteres als BLOB einlesen. Zeitraubend ist das häufige Anfügen kurzer Strings an einen sehr langen.

Analyse

Für eine quantitative Analyse habe ich ein kleines Programm geschrieben, das in einer Schleife einen kurzen String mit einer Länge von 10 Zeichen an den String sOut anfügt. Einmal pro 100 Durchläufe wird die Zeit gemessen und in eine CSV-Datei exportiert. Heraus kommt folgendes Diagramm:

StringAppend Time Length Diagram

Man sieht einen scharfen Knick bei einer Stringlänge von 500.000 Zeichen ab dem das Anfügen weiterer Stringparts wesentlich länger dauert  (im Debug-Mode beginnt der Knick übrigens schon bei 100.000 Zeichen).

String-Beschleuniger

Fügt man die Stringparts nicht direkt dem Output-String an, sondern an einen „Zwischenstring“, der erst ab einer bestimmten Länge N dem Output-String angefügt wird, kann man den Vorgang insgesamt beschleunigen. Den optimalen Wert für N habe ich durch eine Testreihe ermittelt. Er liegt zwischen 10.000 und 20.000, wie man in der folgenden Grafik sieht. Es dauert dann nur noch ca. 13 Sekunden, bis ein 10 MByte großer String aus insgesamt einer Million String-Anfügungen zusammengebaut ist.

StringBuilder Performance Run

StringBuilder Performance Run

StringBuilder

Das oben beschriebene Verhalten habe ich in eine Klasse StringBuilder gepackt: Deren Methoden Append(…) fügt Teilstrings an, mit ToString() holt man den fertigen String ab. Lenght() liefert die aktuelle Länge des Gesamtstrings und Clear() setzt ihn zurück. Den Programmcode des StringBuilders inklusive der Performance-Tests könnt ihr herunterladen.

Download

StringBuilderPerfomanceTests.zip

Happy coding

Boundaries of Number in Gupta

Basically, the Number data type is a fine thing in Gupta. You don’t have to deal with int, float, double, decimal etc. as with many other programming languages. There is only Number. In the daily routine of a developer that fits very well. But some days are different. Some days you reach a limit. Recently that happened again.

Number as Bit Field

It is not uncommon to combine several bit flags in one Number variable. Usually you query this with
If( nSomeFlags & SOME_SettingsFlag)

where SOME_SettingsFlag is a constant with a value of 2 ^ n.

Recently we assigned a value of 2 ^ 33 to the SOME_SettingsFlag constant. No problem for a Number variable itself. But when applied to the &-Operator we got a result of 0 in every case.

Oops.

A quick look at the help file – looking up operator „&“ as well as data type „Number“: unfortunately nothing about value ranges in which they work reliably there. So I did a little research.

& and | work with 4 bytes

For the bitwise AND and OR operators (& and |) it was easy to find out: They work in the range from 0x00000000 to 0xFFFFFFFF. Everything above is cut off.

Number reliable up to 52 Bits

What is the largest integer that one can store in Number? Because the Number type is based on floating-point number, the answer depends on the length of their mantissa. A short test in the debugger shows that the representation of numbers bigger than 2 ^ 52 shows up in exponential notation in the variable watch. A look into Wikipedia substantiates the suspicion: the standard IEEE 754 floating point numbers of type double provides 52 bits for the mantissa, eleven for the exponent, and one for the sign – making a total of 64 bit. In principle, you can store integer numbers with up to 52 bits. Therefor the value range is between +-(2^53-1) or +-9.007.199.254.740.991 or approximately plus minus nine quadrillion.

Man Proposes

While creating a function for bitwise operations for numbers > 32-bit I have written the following line
Set nLower = nOperand & 0xFFFFFFFF

with the following result: When testing with nOperand = 2 ^ 52 Gupta runtime throws an error.

Eh?

Assigning nOperand = 2 ^ 33 returns 0 without any error message although even this one is too large for the &-operator. Further tests have shown that one gets no error message for numbers up to 48 bit, everything above is producing one.

Gupta Disposes

The &-operator has three value ranges for it’s operands

  1. 0 – 2^32 – works flawlessly
  2. 2^33 – 2^48 – ignores bits beyond 32
  3. > 2^48  – throws an error message

Conclusion

While you may use integers up to +-2 ^ 53-1 with Gupta Number however it is advisable to limit it’s use to 32 bit. Because the integer operators work only with up to 4 bytes. Also the Windows message parameter wParam, lParam, and the return value are limited to 32-bit.

Happy coding.