Dictionary (Radix Tree) Source Code Test Program Random Entries

URI:	http://herbert.gandraxa.com/herbert/dic_test_random.asp
Link template:	<a href="http://herbert.gandraxa.com/herbert/dic_test_random.asp">Dictionary (Radix Tree) Source Code Test Program Random Entries</a>
Link symbols:	On current page | On this site | On external site | Wikipedia article | ZIP archive | PDF | E-Mail

---

Article

Organization

Home » Linoleum Source Code » Dictionary (Radix Tree) » Source Code Test Program Random Entries

Scope

This is the source code of the Dictionary (Radix Tree) Test Program for Random Entries, testing the Dictionary (Radix Tree) library, implemented in the Linoleum programming language.

Author

Herbert Glarner

---

Usage

This test program tests long-term functionality of the Dictionary (Radix Tree) library.

Make sure you have the library named dic.txt in the same folder as this test program before assembling the latter.

---

Source Code

(Test application, using the Dictionary Routines "DIC.txt".)

(*****************************************************************************)
(Interpreting the test screen:

DICTIONARY

1st bar:    Number of leaves in the DIC's radix tree, 0<------->1M
            Should always be around 50%
2nd bar:    Number of internal nodes in the DIC's radix tree, 0<------->1M
            Should be close to the 1st bar, just a bit below, never above
3rd bar:    Prediction quality, 0%<------->100%
            Being random on binaries, expect just slightly better than 50%

DYNAMIC STORAGE ALLOCATION

4th bar:    Used memory units, 0<------->22MU
            Will be close to max. The less, the better. However there is a
            theoretical potential to need 38 MU. Hitting the right edge =
            'Out of Memory' {not of your machine's RAM, only of what we
            allocated for the DIC}.
5th bar:    Fragmentation, i.e. free units within allocation, 0%<------->100%
            Sets the fragmentation in relation to the allocated memory. The
            less the better.

COUNTER

Yellow symbols:     Counting million loop iterations, 0...9 symbols
Green symbols:      Counting ten million loop iterations, 0...9 symbols
Red symbols:        Counting hundred million loop iterations, 0...9 symbols
Magenta symbols:    Counting billion loop iterations, 0...25 symbols

I went to 6.759 billion loop iterations. Beware from breaking records, though:
this test program was not written for speed but for visual feedback ;)

(*****************************************************************************)
(Test Scenario:

Used abbreviations in this scenario description:
ME:  Mega Entries = 1,048,576 Entries. An 'Entry' is an item stored into the
     dictionary, identificable by its key, which is a bitstream of arbitrary
     length.
MU:  Mega Units = 1,048,576 Units = 4 MB
PRN: Pseudo Random Number, a 32 bit value as delivered by the RNG library
RNG: Random Number Generator
EN:  Entry Number, in this test setup a number 0...1,048,575 to identify one
     of the 'slots' managing the dictionary's entries by this test program.
     Note, that the concept of a 'Entry Number' does not exist in the DIC
     library itself: it's just introduced in this test program to facilitate
     testing.

I. Setting up a test environment:

1. Create management vector of 10,485,760 units for 1 ME = 1,048,576 entries at
   10 units each, each of these units being a 'slot' for a dedicated dictionary
   entry holdig the entry's key length in bits and the bistream forming the key.
2. Init DIC with approx 22 MU {see discussion [1] below for the reason of this
   value} to hold an average of 1 ME with random key lengths and random user
   data size.
3. Init the RNG Library.
4. Setting up a visualization screen.

II. Permanent Loop, to be left after hitting any key:

1. Get a PRN, let's call it the 'Control PRN'.
2. The last 20 bits of the Control PRN identifies the entry number EN to be
   used, i.e. a number in the range 0...1,048,575.
3. We test the first unit of EN 0...1,048,575 for 0.
   A. If EN 0...1,048,575 is 0 = there is no such entry yet/anymore:
      a. The first 8 bits of the Control PRN, plus a completely arbitrary
         minimum length of 17 bits to ensure that we don't have excessive
         'Key Already Exists' errors, gives the new entry's key length
         17+0...17+255 bits, i.e. max. 9 units. These 9 units are the reason
         for the 'slot size' of 10 units: 1 unit to store the key length, and
         9 units for the key itself.
      b. Into vector address EN*10+0 store the key length 17...272 bits. This
         identifies the slot as being in use, i.e. indicates an existing entry
         in the dictionary.
      c. Create 1...9 additional PRNs as per the new entry's key length. These
         PRNs form the future entry's key. Store the key into vector address
         EN*10+1 and following units.
      d. Bits 23...20 of the Control PRN plus a completely arbitrary 3 gives us
         the length of the user data segment in units, i.e. 0+3...15+3 units.
      e. Use 'Dic Add Entry' with above specifications, i.e. random-length key
         length, random key, random userdata segment size. There are two
         outcomes which need treatment:
         --> Key already existing = reset the first unit of the entry's slot to
             0 to make it 'empty' again, as no such key was inserted into the
             DIC, then count the occurence and forget about the entry; continue
             to loop.
         --> All other errors = report error and stop.
   B. If EN 0...1,048,575 is not 0 = such an entry already exists:
      a. In vector address EN*10+0 is the key length 17...272 bits
      b. In vector address EN*10+1 and following is the bitstream of the key:
         this can consume up to 9 units.
      c. Use 'Dic Remove' on that key with the given keylength.
         --> All errors = report error and stop.
      d. Set vector address EN*10+0 to 0 = ready to accept new entry.
4. All now and then, i.e. all 4k activities, visualize something to have
   something to stare at and to confirm that the test program still 'does
   something': visualize a counter. Show the number of DIC entries: leaves and
   internal nodes separately. Also include some DSA statistics to see how it
   works with the DIC library.
5. Loop until arbitrary key is hit.

III. Output some statistics in the registers

[1] How much space shall we give the DIC library to manage all this randomness?
- There are max. 1,048,576 entries, average will be half = 524,288 entries all
  the time.
- Each entry has a maximum user data area of 3+15=18 units, in average
  3+[0+15]/2=10.5 units.
- Each entry has a key length of max. 17+255b = 9 units, in average
  17+[0+255]/2=4.52 units.
- But: there are also internal nodes holding prefixes common to their children.
  With random numbers we can assume a quite well balanced radix tree, so about
  the same number of internal nodes as the average number of entries can be
  expected = 524,288 internal nodes in average.
- Each node has 5 units management information, thus in average 1,048,576 nodes
  x 5 units DIC management data = 5,242,880 units.
- Each node requires 4 units DSA management data = 4,194,304 units in average.
- Each individual chunk length of 1...9 units key bitstream and 3...18 units
  requires an AVL node managed by the DSL library, and due to the large average
  entry volume in average there will be an AVL node for all those lengths 1...18,
  thus 18 AVL nodes x 6 units = 108 units. No issue to really bother about.
- All in all we have the following storage requirement:
  maximum 18.0*1,048,576 + [9.00+5+4]*1,048,576 + 108 = 37,748,844 units
  average 10.5*  524,288 + [4.52+5+4]*1,048,576 + 108 = 19,681,772 units
- Let's brag a bit with the DSA quality: If the DSA does its job well and we
  don't have too much fragmentation, then we should go along well with the
  just calculated estimated average of 20 million units plus a small reserve
  of 10% = totally 22 million units [88 MB]. Note that if there coincidentially
  is a random sequence suddenly filling up many more than 524,288 entries, or
  a sequence generating a series of overly long keys and/or user data segments,
  then we end up with an 'Out of Memory' error as well: to be on the safe side
  we should reserve 38 million units plus space for unavoidable fragmentation.
  Such we also rely on a well working RNG library providing well-distributed
  pseudo random numbers. If all this is the case, this would speak for the
  libraries' quality. Therefore we try to go along with a modest 22 MU rather
  than a safe 38 MU. - Btw: I am pretty confident we could go along even with
  a tiny reserve of only 5% = a total of 21 MU, but since this is going to be
  a longtime test, I won't challenge chance too much: how annoying to wake up
  after a nightlong unattended test and see an 'Out of Memory' after 5 billion
  iterations rather than a still running visualization screen. However, if you
  try, tell me if I was wrong and after how many iterations ;)

(*****************************************************************************)

"libraries"

    (=========================================================================)
    (Dictionary; the library which is tested with this test program.)
    (-------------------------------------------------------------------------)
        DIC;
    (=========================================================================)

    (=========================================================================)
    (RNG Random Number Generator)
    (-------------------------------------------------------------------------)
    (Used as explained in this file's header under 'Test Scenario'. Available
    at http://herbert.wikispaces.com/MT19937)
    (-------------------------------------------------------------------------)
        RNG;
    (=========================================================================)

(*****************************************************************************)
"directors"
        program name = { DIC Test };
        unit = 32;

    (=========================================================================)
    (Test screen reflecting what's allocated and what's free)
    (-------------------------------------------------------------------------)
        display width = DIC TEST SCREEN WIDTH;
        display height = DIC TEST SCREEN HEIGHT;
    (=========================================================================)

(*****************************************************************************)
"constants"                             (Convention: "DIC ...", UPPER CASE)

    (=========================================================================)
    (Define the size of the testing screen here. The topmost 5*16 pixels are
    used to draw 5 bars measuring different DIC and DSA qualities. The next 4
    'rows' are used to draw symbols acting as loop counters.)
    (-------------------------------------------------------------------------)
        DIC TEST SCREEN WIDTH = 512;
        DIC TEST SCREEN HEIGHT = 9 mtp 16;      (9 'lines' at 16 pixels)
    (=========================================================================)

    (=========================================================================)
    (Requested memory area for our Dictionary)
    (-------------------------------------------------------------------------)
        DIC TEST MAX ENTRIES = 1024 mtp 1024;               (1 ME)
        DIC TEST RAM SIZE = 22 mtp DIC TEST MAX ENTRIES;    (22 MU = 88 MB)
    (-------------------------------------------------------------------------)
    (How many bytes can be represented per pixel)
        DIC TEST BYTES PER PIXEL = DIC TEST RAM SIZE div
                                   DIC TEST SCREEN WIDTH;
    (=========================================================================)

    (=========================================================================)
    (Visualization constants)
    (-------------------------------------------------------------------------)
    (See comments in the visualization subroutine 'Dic Test Visualize'.)
        DIC TEST FILL BAR HEIGHT = 16;
    (-------------------------------------------------------------------------)
    (How many entries can be represented per pixel)
        DIC TEST ENTRIES PER PIXEL = DIC TEST MAX ENTRIES div
                                     DIC TEST SCREEN WIDTH;
    (=========================================================================)

(*****************************************************************************)
"variables"                             (Convention: "dic ...", lower case)

    (=========================================================================)
    (Visualization)
    (-------------------------------------------------------------------------)
    (Some counters merely to draw a non-text counter)
        dic test loop counter = 0;      (Counts the iterations below millions)
        dic test loop millions = 0;     (Counts whole millions of iterations)
        dic test loop tenmillions = 0;  (etc.)
        dic test loop hundredmillions = 0;
        dic test loop billions = 0;
        dic test symbols color = 0;     (Each magnitude in own color)
        dic test visualizations = 0;    (Calls to the visualization routine)
        dic test last millions = 0;     (Spares superfluous symbols drawing)
    (=========================================================================)

    (=========================================================================)
    (Just out of curiosity we count some values. Upon termination they will be
    displayed in registers C, D and E, unless there was an error.)
    (-------------------------------------------------------------------------)
        dic test added = 0;             (Successfull 'Dic Add Entry' calls)
        dic test removed = 0;           (Successfull 'Dic Add Remove' calls)
        dic test existing keys = 0;     ('Dic Add Entry' rejects double keys)
    (=========================================================================)

(*****************************************************************************)
"workspace"                             (Convention: "dic ...", lower case)

    (=========================================================================)
    (Display area)
    (-------------------------------------------------------------------------)
        dic test window = DIC TEST SCREEN WIDTH mtp DIC TEST SCREEN HEIGHT;
    (=========================================================================)

    (=========================================================================)
    (Random Number initialization)
    (-------------------------------------------------------------------------)
        dic test rng init key = 4;
    (=========================================================================)

    (=========================================================================)
    (This is a pseudo 'object' vector. In reality, this contains the data of
    your 'object', be that a player's infos in a game, a database record,
    whatever. In this test setup, objects have a random length of 3...18 units;
    in reality they may have just any length, as long as the provided RAM is
    large enough.)
    (-------------------------------------------------------------------------)
        dic test object = 18;
    (=========================================================================)

    (=========================================================================)
    (Into the following vector a new key is calculated. It can be at most 9
    units long.)
    (-------------------------------------------------------------------------)
        dic test key = 9;
    (=========================================================================)

    (=========================================================================)
    (This is the management vector which contains up 1 Mega-Entries with
    10 units each: for each entry, the first unit stores the key length encoded
    as a bitstream in the next max. 9 units. Such a storage is needed to be
    able to identify an entry by its key in order to remove the entry. In a
    real application, such overhead is not needed, of course, as the DIC itself
    holds all information.)
    (-------------------------------------------------------------------------)
        dic test node mgmt = 1024 mtp 1024 mtp 10;  (10 MU = 40 MB)
    (=========================================================================)

(*****************************************************************************)
"programme"                             (Convention: "Dic ...", Mixed case)

    (*************************************************************************)
    (I. SETTING UP THE TEST ENVIRONMENT)
    (*************************************************************************)

    (=========================================================================)
    (Screen init)
    (-------------------------------------------------------------------------)
        [Display Origin] = dic test window;     (Defined in the workspace area)
    (=========================================================================)

    (=========================================================================)
    (Providing some RAM for the Dictionary.)
    (-------------------------------------------------------------------------)
        D = DIC TEST RAM SIZE;          (Number of units)
        => Dic Create;
        ? ok -> Dic Test Dic Created;
        A = 1;                          (Testing phase)
        B = [dic error];                (What error occured)
        -> Dic Test Stop;
    "Dic Test Dic Created"
    (=========================================================================)

    (=========================================================================)
    (Initializing the Random Number Generator.)
    (-------------------------------------------------------------------------)
        [dic test rng init key plus 0] = 123h;
        [dic test rng init key plus 1] = 234h;
        [dic test rng init key plus 2] = 345h;
        [dic test rng init key plus 3] = 456h;

        E = dic test rng init key;      (Address of init key)
        D = 4;                          (Length of init key)
        => Rng Init;
    (Now random Numbers can be produced by simply calling '=> Rng Long'. Each
    call will provide a differnt 32 bit number into E.)
    (=========================================================================)


    (*************************************************************************)
    (II. THE INFINITE LOOP. Break with any key.)
    (*************************************************************************)
    "Dic Test Infinite Loop"

    (=========================================================================)
    (Check if the user aborts by hitting any key.)
    (-------------------------------------------------------------------------)
        [Console Command] = GETCONSOLEINPUT;
        isocall;
        ? ok -> Dic Test Exit;
    (=========================================================================)

    (=========================================================================)
    (Visualize something to confirm that 'it still runs'.)
    (-------------------------------------------------------------------------)
    (Visualization is done only once in about 4k loops, otherwise most of the
    time would be spent on drawing rather than on actually testing the lib.
    For this reason, we implement a loop counter. Anding the last 12 bits
    gives us a range of 0...4095. Only if we are at 0 we draw. We do this in
    a subroutine to have it out of the way.)
        [dic test loop counter] + 1;    (One iteration more)

    (For visualization reasons we count whole millions separately. When we
    reach a million, the normal counter is reset to 0. Each magnitude beyond
    millions is counted separately to facilitate visualization with symbols.
    Beyond approx. 25 billion there is no more space for the billion symbols:
    that's the point where we stop with the test to prevent a crash from
    drawing symbols beyond the screen area. However, feel free to implement
    also a 10 billion counter etc. if you really need more of this ;)
        ? [dic test loop counter] < 1 000 000 -> Dic Test No Million Update;
        [dic test loop millions] + 1;   (One million loops more)
        [dic test loop counter] = 0;    (Reset basic counter)

        ? [dic test loop millions] < 10 -> Dic Test No Million Update;
        [dic test loop tenmillions] + 1;
        [dic test loop millions] = 0;

        ? [dic test loop tenmillions] < 10 -> Dic Test No Million Update;
        [dic test loop hundredmillions] + 1;
        [dic test loop tenmillions] = 0;

        ? [dic test loop hundredmillions] < 10 -> Dic Test No Million Update;
        [dic test loop billions] + 1;
        [dic test loop hundredmillions] = 0;

    (Ok, ok, we stop here and enforce terminattion after 25.999 billions ;)
        ? [dic test loop billions] = 26 -> Dic Test Exit;
    "Dic Test No Million Update"

        A = [dic test loop counter];
        A & 0000 0FFFh;                         (last 12 bits  0...4095)
        ? A != 0 -> Dic Test No Visualization;  (Only if 0 we visualize)
        => Dic Test Visualize;
    "Dic Test No Visualization"
    (=========================================================================)

    (=========================================================================)
    (Determine on which of the 1 million entries we want to operate this time.)
    (-------------------------------------------------------------------------)
    (Get a Pseudo Random Number PRN)
        => Rng Long;                    (32 bit PRN available in E)
        A = E;                          (Save the PRN)

    (The PRN provides us with 3 different values in 3 bitfields. The bitfields
    are: bits 31:24 = a 8 bits biased key length in bits; 23:20 = a 4 bits
    biased userdata size in units, bits 19:0 = a 20 bits Entry Number. First
    extract only the the Entry Number on which we want to perform an action.)
        E & 000F FFFFh;                 (Bits 19:0 = 0...1,048,575)
        E * 10;                         (10 units Test Management per Entry)
        E + dic test node mgmt;         (Address is in Test Management Area)
    (=========================================================================)


    (=========================================================================)
    (Either add a new entry, or remove an existing entry)
    (-------------------------------------------------------------------------)
    (If the first unit starting at [E plus 0] is 0, then this entry currently
    is empty. In this case we can provide a new entry into it.)
        ? [E plus 0] = 0 -> Dic Test Add Entry;

    (The unit is not empty, thus it must be the length of an already existing
    entry. The length is measured in bits.)

    (INFO: When does this happen first? With approx 1 million possible 20 bit
    keys after approx 500,000 keys? No way: we will have the first such event
    already after 1,988 successfull calls to 'Dic Add Entry': this is a typical
    effect of the Birthday Paradoxon. Search the net for aditional infos about
    this.)
        (-> Dic Test Remove Entry;)
    (=========================================================================)

    (=========================================================================)
    (Removing an existing entry from the dictionary)
    (-------------------------------------------------------------------------)
    (In [E plus 0] is the length of the bistream acting as key which needs to
    be removed. in [E plus 1] is the bitstream itself, which is the key of the
    existing node. That's all we need to know to remove that entry from the
    dictionary, including its 'data object'. Let's remove it.)
    (-------------------------------------------------------------------------)
    ("Dic Test Remove Entry")
        A = E; A + 1;                   (Address of saved key)
        B = [E plus 0];                 (Length of key in bits: 17...272 bits)
        => Dic Remove Entry;
        ? ok -> Dic Test Remove Entry Removed;
    (-------------------------------------------------------------------------)
    (That really should not happen...)
        A = 2;                          (Testing phase)
        B = [dic error];                (What error occured)
        -> Dic Test Stop;               (Break the loop and stop the program)

     "Dic Test Remove Entry Removed"
    (By setting the removed entry's key length unit in this test's management
    area to 0 we declare it to be a free entry: such it can be used again to
    add a new entry with a different key, until it will also be removed, etc.)
        [E plus 0] = 0;                 (Can be re-used now)

    (Let's loop until either the user feels to break by hitting any key or an
    error occurs. But before that, we count the successful operation.)
        [dic test removed] + 1;         (Count success)
        -> Dic Test Infinite Loop;
    (=========================================================================)

    (=========================================================================)
    (Adding an entry to the dictionary)
    (-------------------------------------------------------------------------)
    "Dic Test Add Entry"

    (The management units at E indicate that the node is free, because [E] is
    0. The PRN was saved into A. Its 8 MSBs give us the biased bit length of
    the bistream which forms the key. Adding a completely arbitrary value of
    17 bits decreases the change to have 'Key Already Existing' returned.
    Don't increase this value here witout also changing the slot size to hold
    the keys in this test environment; also you need to modify the storage
    allocation if you increase this value.)
        B = A;                          (The PRN was saved into A, get it)
        B > 24;                         (Key length 0...255 bits)
        B + 17;                         (Key length 17...272 bits)

    (The key length B is stored into [E plus 0]: we need to remember its length
    to later on issue a call to 'Dic Remove Entry', as soon as the same entry
    number is generated again.)
        [E plus 0] = B;                 (Store the key length 17...272 bits)

    (In order to provide a random bitstream with the RNG library, we need to
    know, how many units the E bits need. This can easily be calculated with
    {E + 31}/32.)
        C = B;                          (Key length in bits)
        C + 31;                         (Round up)
        C > 5;                          (Needed units)

    (The bitstream forming the entry's key of B bits needs C units. Thus, to
    generate a random key of C units we need C Random Numbers of 32 bits, which
    we generate now with the RNG library. The units are store consecutively
    into the vector 'dic test key' which will be passed to 'Dic Add Entry'.
    Because we need to keep track of the key in order to destroy this entry
    later on, a copy is kept in the management area, just after the entry's
    key length, i.e. at [E plus 1] and following units. We use C as the
    counter: it is always at least 1 and never greater than {272 + 31}/32 =
    9 units.)
        D = E;                          (Address of entry start)
        E -->;                          (Need address in E back)
        A -->;                          (Need saved PRN back)
        A = dic test key;               (Address of key vector)
    "Dic Test Add Entry Add Key Unit"
        D + 1;                          (Address to store the next PRN)
        => Rng Long;                    (32 bit PRN available in E)
        [A] = E;                        (Store 32 bits of key's bitstream)
        [D] = E;                        (Also store in management area)
        A + 1;                          (Next unit to store the PRN)
        C ^ Dic Test Add Entry Add Key Unit;    (Repeat until key complete)
        <-- A;                          (Restore saved PRN)
        <-- E;                          (Restore address of entry start)

    (Now the entry's 10-units managament area at E has 1 unit for the number
    of bits the key consists of, and a random bitstream of 1...9 units at E+1.
    These informations are good for the key, but we want also a random data
    chunk. There are still 4 unused bits 23:20 in the original PRN still being
    saved in A. Let's get those bits to determine the size of our 'object',
    i.e. 0...15 units. An additional 3 units are added to grant a minimum size
    of 3 units. Don't increase this value 3 here without also modifying the
    storage allocation.)
        A > 20;                         (12 right-aligned bits remain)
        A & 1111b;                      (We need only 4 of them, 0...15)
        A + 3;                          (3...18 units length for 'object')
    (-------------------------------------------------------------------------)
    (Now we have everything what's needed to create a dictionary entry:
    several units of the key in the vecor 'dic test key', its length in bits
    in [E], the length of the object in units is in A, and the object data is
    at 'dic test object'. Note, that we don't care for a content in the object
    vector. In a real application, it is here where your object structure goes,
    whatever it may contain. These 4 arguments are passed in registers now.)
        C = dic test object;            (Address of the 1st unit of the data)
        D = A;                          (Length of data in units)
        A = dic test key;               (Address of the 1st unit of the key)
        B = [E plus 0];                 (Length of key in bits)
        => Dic Add Entry;               (Store into the dictionary)
        ? ok -> Dic Test Add Entry Added;
    (-------------------------------------------------------------------------)
    (Oops an error. Note, however, that we don't treat non-unique keys as an
    error here. Everything else is a real error, though, and beraks the
    loop.)
        ? [dic error] != DIC ERR KEY NOT UNIQUE -> Dic Test Add Entry Error;

    (This was an attempt to add an entry with a key which already exists. Such
    an attempt is rejected by the DIC library: keys must be unique. The keys
    are created randomly and sooner or later we will ranomdly generate double
    entries. Already pretty soon, actually: the 11,289th entry is the first
    attempt to add an entry with an already existing key: it's a short 22-bits
    key. - Because we already stored the key length in our entries management
    area, the entry was speculatively marked as 'present' already, although
    the library rejected it: we need to clear that length again to give later
    attempts a chance to add a valid entry.)
        [E plus 0] = 0;                 (Reset length = clear entry)
        [dic test existing keys] + 1;   (Count such occurences)
        -> Dic Test Infinite Loop;      (Then continue to loop)

    "Dic Test Add Entry Error"          (Real errors)
        A = 3;                          (Testing phase)
        B = [dic error];                (What error occured)
        -> Dic Test Stop;               (Break the loop and stop the program)
    "Dic Test Add Entry Added"

    (Everything fine? Great, let's loop happily along until the user feels to
    break by hitting any key. But before that, we count the successful
    operation.)
        [dic test added] + 1;           (Count success)
        -> Dic Test Infinite Loop;
    (=========================================================================)



    (*************************************************************************)
    (III. TERMINATING)
    (*************************************************************************)

    (=========================================================================)
    (Address we jump to if we exit on user request = hit any key.)
    (-------------------------------------------------------------------------)
    "Dic Test Exit"

    (Destroying the Dictionary. No input parameters required. No result
    provided. No errors possible. Still needs to be called to return the
    allocated memory to the OS.)
        => Dic Destroy;
    (-------------------------------------------------------------------------)
    (Output Some statistical data.)
        A = 99;                         (A = 99 = all ok, otherwise failure)

    (All the following counters are subject to overflow beyond FFFFFFFFh,
    although an overflow does not cause any harm beyond making interpretation
    of the final output values more difficult. However, overflowing means to
    run the test for approx. 8.6 billion times, i.e. 2*FFFFFFFFh, which would
    take quite a while: this test program is not designed for speed but for
    visualization of background quality.)
        C = [dic test added];
        D = [dic test removed];
        E = [dic test existing keys];

    (Both the DIC and DSA libraries provide statistical values which you might
    want to retrieve and display instead of above statics. You can do this here.)

        show registers;
    (=========================================================================)

    (=========================================================================)
    (Address we jump to if there is an error. In A is the testing phase, in
    B is the error number.)
    (-------------------------------------------------------------------------)
    "Dic Test Stop"
        show registers;
    (=========================================================================)

(*****************************************************************************)
(This is the visualization routine. It is implemented as a routine to keep it
out of the way of above program's main stream.)

"Dic Test Visualize"

    (=========================================================================)
    (Called each 4k loop iterations to visually confirm to the user that the
    program still runs.)
    (-------------------------------------------------------------------------)
    (Some evaluations are done less frequently because they cost much of time.
    For those this counter exists: they will be executed as a fraction of
    calls to this routine.)
        [dic test visualizations] + 1;  (Calls to the visualization routine)
    (-------------------------------------------------------------------------)
    (The topmost DIC TEST FILL BAR HEIGHT pixels of the screen are used to draw
    a colored 'fill bar' of current dictionary entries. This height originally
    is 16 pixels. The bar grows from the left edge = 0 entries to the right
    edge = DIC TEST MAX ENTRIES entries, which in the original test file is
    1024*1024. Since we have a limited screen width only, we need to divide the
    current number of entries with the number of entries fitting in a pixel,
    i.e. DIC TEST MAX ENTRIES/DIC TEST SCREEN WIDTH to get the number of
    horizontal pixels which we want to color. The expression '1,048,576 /
    DIC TEST SCREEN WIDTH' is defined as a constant, its name is 'DIC TEST
    ENTRIES PER PIXEL'. The number of actual entries could be calculated by
    using the two counters [dic test added] and [dic test removed]: the
    difference is the current number of existing entries. However, we would
    need to care for overflow handling in really long termed tests. There's an
    easier way though to obtain the same number without the overflow issue:
    The DIC library maintains a variable [dic number of leaves] which is
    identical with [dic test added]-[dic test removed]. Due to this test's
    design the existing entries very soon will grow to DIC TEST MAX ENTRIES/2
    and then fluctuate around that value.)
        A = [dic number of leaves];     (Number of currently existing entries)
        A / DIC TEST ENTRIES PER PIXEL; (Required horizontal pixels)
        C = A;                          (Save this number, need often)

        E = dic test window;            (Upper left edge of fill bar)
    (Loop over the whole bar's height)
        B = DIC TEST FILL BAR HEIGHT;
    "Dic Test Visualize Leaves Bar Line"

    (Draw A green pixels to symbolize the fill bar)
    "Dic Test Visualize Leaves Bar Exist"
        [E] = 00 008000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Leaves Bar Exist;

    (The rest of the line consists of DIC TEST SCREEN WIDTH-C black pixels:
    such we cancel out a formerly longer bar.)
        A = DIC TEST SCREEN WIDTH;
        A - C;
    "Dic Test Visualize Leaves Bar Empty"
        [E] = 00 000000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Leaves Bar Empty;

    (Restore A for the next line)
        A = C;

    (Next line of the fill bar)
        B ^ Dic Test Visualize Leaves Bar Line;
    (-------------------------------------------------------------------------)
    (There's another value which is of interest: the number of internal nodes
    which the DIC library has to maintain in order to keep its radix tree.
    Whereas [dic number of leaves] keeps a counter to 'real' entries only, the
    counter [dic number of nodes] counts /all/ nodes of the tree, whether
    internal only or a real leaf. Thus a subtraction tells us the internal nodes
    only, which we visualize now exactly as above, only that we draw them a bar
    lower and in red rather than in green. Typically, this bar is just somewhat
    smaller than the first bar with the number of leaves. This is because the
    radix tree will be pretty well balanced due to the random bitstreams. The
    bar /never/ may exceed the width of the leaves bar though: this would mean
    that we had more internal nodes than leaves, which conceptionally is not
    possible in radix trees: if it nevertheless happens, then there is a
    programming flaw, missing the chance to coalesce stacked internal nodes.
    Should the bar shrink to a far lesser size than the leaves bar, this would
    indicate that most nodes are real leaves. This happens frequently with e.g.
    ASCII text files, where the left branch of nodes is favoured over the right
    branch, because lowercase ASCII characters start out with a 0 bit. However,
    in this test setup it is unlikely to happen. If it still does, it must be
    interpreted as a bad quality random number generation, which is extremely
    unlikely to be the case.)
        A = [dic number of nodes];      (All nodes INCLUDING leaves)
        A - [dic number of leaves];     (Internal nodes only)
        A / DIC TEST ENTRIES PER PIXEL; (Required horizontal pixels)
        C = A;                          (Save this number, need often)
    (E is already the position to draw the next pixel to, no need to calculate
    the value.)

    (Loop over the whole bar's height)
        B = DIC TEST FILL BAR HEIGHT;   (All bars have the same height)
    "Dic Test Visualize Nodes Bar Line"

    (Draw A red pixels to symbolize the internal nodes bar)
    "Dic Test Visualize Nodes Bar Exist"
        [E] = 00 FF0000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Nodes Bar Exist;

    (The rest of the line consists of DIC TEST SCREEN WIDTH-C black pixels:
    such we cancel out a formerly longer bar.)
        A = DIC TEST SCREEN WIDTH;
        A - C;
    "Dic Test Visualize Nodes Bar Empty"
        [E] = 00 000000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Nodes Bar Empty;

    (Restore A for the next line)
        A = C;

    (Next line of the fill bar)
        B ^ Dic Test Visualize Nodes Bar Line;
    (-------------------------------------------------------------------------)
    (A third bar measures the quality of branch prediction. With random data,
    as used in this test, this value will fluctuate around 50%.)

(To avoid overflows we would need to reset the counters when they exceed
32 bit, i.e. as soon as the total is smaller than the correct predictions.
However, this would cause sudden rejumps to 50%. It is better to divide both
counters by the same constant in order to keep the relation.)
? [dic number correct pred] + FFC0 0000h -> Dic Test Visualize Large Values;
? [dic number incorrect pred] - FFC0 0000h -> Dic Test Visualize Small Values;
"Dic Test Visualize Large Values"   (Values which cause overflow when mtp 512)
[dic number correct pred] > 12;
[dic number incorrect pred] > 12;
"Dic Test Visualize Small Values"

    (The variable [dic number correct pred] is set in relation to the sum of
    the two variables [dic number correct pred] and [dic number incorrect pred].)
        C = [dic number correct pred];
        A = C;                              (Correct predictions only)
        C + [dic number incorrect pred];    (All predictions)
        ? C > 0 -> Dic Test Visualize Values Valid;
    (Better omit an invalid division, but adjust for intended bar height)
        E + DIC TEST FILL BAR HEIGHT mtp DIC TEST SCREEN WIDTH;
        -> Dic Test Visualize Memory Quality;
    "Dic Test Visualize Values Valid"
        A * DIC TEST SCREEN WIDTH;          (100% is whole screen width)
        A / C;                              (Effective percentage * screen width)
        C = A;                          (Save this number, need often)
    (E is already the position to draw the next pixel to, no need to calculate
    the value.)

    (Loop over the whole bar's height)
        B = DIC TEST FILL BAR HEIGHT;   (All bars have the same height)
    "Dic Test Visualize Predictor Bar Line"

    (Draw A yellow pixels to symbolize the prediction quality bar)
    "Dic Test Visualize Predictor Bar Exist"
        [E] = 00 FFFF00h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Predictor Bar Exist;
    (The rest of the line consists of DIC TEST SCREEN WIDTH-C black pixels:
    such we cancel out a formerly longer bar.)
        A = DIC TEST SCREEN WIDTH;
        A - C;
    "Dic Test Visualize Predictor Bar Empty"
        [E] = 00 000000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Predictor Bar Empty;
    (Restore A for the next line)
        A = C;

    (Next line of the predictor bar)
        B ^ Dic Test Visualize Predictor Bar Line;
    (-------------------------------------------------------------------------)
    "Dic Test Visualize Memory Quality"

    (The following two bars require the call to an expensive function: it is
    called only every 8th time we call this visualization routine, and since
    it is called every 4k loops only, that means that an update occurs every
    32k loops only. If you want the bars progress more smootly, reduce to
    11b = every 4th time, or 1b = every 2nd time, or comment out the following
    instruction altogether to have it done each time. But beware, the call to
    'Dsa Fragmentation' slows the test down significantly.)
        ? [dic test visualizations] + 111b -> Dic Test Visualize No Memory Bars;

    (The next 16 pixels are used to show what percentage of the totally
    allocated memory is actually used. The total allocated memory can be
    obtained by the constant DIC TEST RAM SIZE. The effectively used memory
    can be calculated after a call to 'Dsa Fragmentation', which returns
    various data about the allocated memory.)
        => Dic Local Dsa Data;          (Switch to DIC's local DSA Data)
        => Dsa Fragmentation;
        => Dic Global Dsa Data;          (Switch to DIC's global DSA Data)
        A -->; B -->; C -->;            (Need values also for next bar)

    (Output:    A:  Free and reusable RAM below the memory pool, in units
                B:  Totally allocated and free RAM below the memory pool, units
                C:  Size of memory pool with free RAM, in units
    Used memory is B - A. Similarly to above bars, we need to calculate the width
    of the memory bar such, that complete memory usage means a full bar extending
    to the right edge. The constant DIC TEST BYTES PER PIXEL helps us to calculate
    that width.)
        A - B;
        A +-;
        A / DIC TEST BYTES PER PIXEL;
        C = A;                          (Save this number, need often)
    (E is already the position to draw the next pixel to, no need to calculate
    the value.)

    (Loop over the whole bar's height)
        B = DIC TEST FILL BAR HEIGHT;   (All bars have the same height)
    "Dic Test Visualize Memory Bar Line"

    (Draw A blue pixels to symbolize the used memory bar)
    "Dic Test Visualize Memory Bar Exist"
        [E] = 00 0000FFh;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Memory Bar Exist;

    (The rest of the line consists of DIC TEST SCREEN WIDTH-C black pixels:
    such we cancel out a formerly longer bar.)
        A = DIC TEST SCREEN WIDTH;
        A - C;
    "Dic Test Visualize Memory Bar Empty"
        [E] = 00 000000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Memory Bar Empty;

    (Restore A for the next line)
        A = C;

    (Next line of the fill bar)
        B ^ Dic Test Visualize Memory Bar Line;
        <-- C; <-- B; <-- A;            (Values from 'Dsa Fragmentation')
    (-------------------------------------------------------------------------)
    (The last bar measures the overall fragmentation of the available memory.)
    (Registers: A:  Free and reusable RAM below the memory pool, in units
                B:  Totally allocated and free RAM below the memory pool, units
                C:  Size of memory pool with free RAM, in units
    Calculation of overall fragmentation as a fraction of the screen width:
    A * DIC TEST SCREEN WIDTH / {B + C}. We make sure B+C is not 0. although
    there is no reason that it ever should be 0. However, it's a division, and
    Intel's don't divide by 0. Note, that B + C is not exactly the same as the
    constant DIC TEST RAM SIZE: from the whole allocated RAM, a usually pretty
    small portion is used for the DSA library's AVL manager controlling free
    chunks. DIC TEST RAM SIZE includes this AVL manager, whereas B+C does not.
    Such B+C tells us what effectively is available. However, the AVL manager
    does not require much space with this test scenario : it's max. 108 units
    only having memory chunks between 1 and 18 units.)
        A * DIC TEST SCREEN WIDTH;
        B + C;                          (If 0 we have no fragmentation at all)
        ? B = 0 -> Dic Test Visualize Fragmentation None;
        A / B;
        C = A;                          (Save this number, need often)
    (E is already the position to draw the next pixel to, no need to calculate
    the value.)

    (Loop over the whole bar's height)
        B = DIC TEST FILL BAR HEIGHT;   (All bars have the same height)
    "Dic Test Visualize Fragmentation Bar Line"

    (Draw A cyan pixels to symbolize the fragmentation memory bar)
        ? A = 0 -> Dic Test Visualize Fragmentation Bar None Exist;
    "Dic Test Visualize Fragmentation Bar Exist"
        [E] = 00 00FFFFh;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Fragmentation Bar Exist;
    "Dic Test Visualize Fragmentation Bar None Exist"

    (The rest of the line consists of DIC TEST SCREEN WIDTH-C black pixels:
    such we cancel out a formerly longer bar.)
        A = DIC TEST SCREEN WIDTH;
        A - C;
        ? A = 0 -> Dic Test Visualize Fragmentation Bar None Empty;
    "Dic Test Visualize Fragmentation Bar Empty"
        [E] = 00 000000h;               (Draw pixel)
        E + 1;                          (Next address to draw to)
        A ^ Dic Test Visualize Fragmentation Bar Empty;
    "Dic Test Visualize Fragmentation Bar None Empty"

    (Restore A for the next line)
        A = C;

    (Next line of the fill bar)
        B ^ Dic Test Visualize Fragmentation Bar Line;
    "Dic Test Visualize Fragmentation None"
    (-------------------------------------------------------------------------)
    "Dic Test Visualize No Memory Bars"

    (What follows is drawing the counter symbols.)

    (No need to draw new symbols if nothing changed.)
        ? [dic test last millions] = [dic test loop millions]
                                        -> Dic Test Visualize Counters Drawn;

    (Store the last drawn state so that we can detect if something changed.)
        [dic test last millions] = [dic test loop millions];

    (For every million loops we draw a symbol in the 5th 'line'. The number
    of millions is counted in [dic test loop millions]. However, there are
    more counters, all dealing with a magnitude larger numbers, up to billions.
    We draw them in different colors.)

    (E must be calculated, we possibly skipped drawing the memory bars and thus
    E may not be were we expect it to be.)
        E = 5;                          (Skip space for 4 bars)
        E * DIC TEST FILL BAR HEIGHT;   (All bars have the same height)
        E + 4;                          (4 pixels distance from lowest bar)
        E * DIC TEST SCREEN WIDTH;      (Relative start of actual line)
        E + 1;                          (1 pixel distance from left edge)
        E + dic test window;            (Absolute address for first symbol)

    (Our symbols shall be small squares of DIC TEST FILL BAR HEIGHT-4 pixels
    edge length. There shall be as many symbols as there are whole millions.)
        A = [dic test loop millions];
        ? A = 0 -> Dic Test Visualize Draw No Million Symbols;
        [dic test symbols color] = 00 FFFF00h;  (Yellow for millions)
    "Dic Test Visualize Draw Million Symbol"
    (E is at the start of a symbol, i.e. at its upper left corner. Draw a
    square of DIC TEST FILL BAR HEIGHT-4 pixels edge length.)
        => Dic Test Draw Square;        (Draws square at address E)
    (The next symbol starts 2 pixels to the right of the right edge of the
    just drawn symbol.)
        E + DIC TEST FILL BAR HEIGHT minus 4 plus 2;
        A ^ Dic Test Visualize Draw Million Symbol;
    (No need to update the other symbols)
        -> Dic Test Visualize Counters Drawn;

    "Dic Test Visualize Draw No Million Symbols"
    (We only can have 0 millions at the start or when a new tenmillion symbol
    is needed. In E is the start of the million symbols not needed anymore.
    Clear the DIC TEST FILL BAR HEIGHT minus 4 lines.)
        => Dic Test Clear Symbols;

    (E is already in position to draw the tenmillion symbols now. And such all
    repeats for the tenmillions.)
        A = [dic test loop tenmillions];
        ? A = 0 -> Dic Test Visualize Draw No Tenmillion Symbols;
        [dic test symbols color] = 00 00FF00h;  (Green for tenmillions)
    "Dic Test Visualize Draw Tenmillion Symbol"
        => Dic Test Draw Square;        (Draws square at address E)
        E + DIC TEST FILL BAR HEIGHT minus 4 plus 2;
        A ^ Dic Test Visualize Draw Tenmillion Symbol;
        -> Dic Test Visualize Counters Drawn;
    "Dic Test Visualize Draw No Tenmillion Symbols"
        => Dic Test Clear Symbols;

    (And for the hundredmillions)
        A = [dic test loop hundredmillions];
        ? A = 0 -> Dic Test Visualize Draw No Hundredmillion Symbols;
        [dic test symbols color] = 00 FF0000h;  (Red for hundredmillions)
    "Dic Test Visualize Draw Hundredmillion Symbol"
        => Dic Test Draw Square;        (Draws square at address E)
        E + DIC TEST FILL BAR HEIGHT minus 4 plus 2;
        A ^ Dic Test Visualize Draw Hundredmillion Symbol;
        -> Dic Test Visualize Counters Drawn;
    "Dic Test Visualize Draw No Hundredmillion Symbols"
        => Dic Test Clear Symbols;

    (Eventually for the billions)
        A = [dic test loop billions];
        ? A = 0 -> Dic Test Visualize Draw No Billion Symbols;
        [dic test symbols color] = 00 FF00FFh;  (Magenta for billions)
    "Dic Test Visualize Draw Billion Symbol"
        => Dic Test Draw Square;        (Draws square at address E)
        E + DIC TEST FILL BAR HEIGHT minus 4 plus 2;
        A ^ Dic Test Visualize Draw Billion Symbol;
        -> Dic Test Visualize Counters Drawn;
    "Dic Test Visualize Draw No Billion Symbols"
        => Dic Test Clear Symbols;
    (-------------------------------------------------------------------------)
    "Dic Test Visualize Counters Drawn"

    (Finally draw a vertical bar each eigth of screen width in white lines)
        E = dic test window;            (Upper left edge of fill bar)

        B = 8;                          (4 lines)
    "Dic Test Visualize Draw Line"
        E + DIC TEST SCREEN WIDTH div 8;    (Each eigth of screen width)
    (Draw a vertical line)

    (The 2nd line goes down to the bottom, is also right edge of symbols)
        C = DIC TEST SCREEN HEIGHT;         (Assume is 2nd line)
        ? B = 7 -> Dic Test Visualize Draw Not Second Line;
        C = DIC TEST FILL BAR HEIGHT mtp 5; (5 bars high)
    "Dic Test Visualize Draw Not Second Line"
        E -->;                              (Need E back)
        E -;                                (Line at /end/ not start of eigth)
    "Dic Test Visualize Draw Pixel of Line"
        [E] + 00 FFFFFFh;
        E + DIC TEST SCREEN WIDTH;
        C ^ Dic Test Visualize Draw Pixel of Line;
        <-- E;
        B ^ Dic Test Visualize Draw Line;

    (A last horizontal white lien to optically divide bars from counter symbols)
        E = dic test window;            (Upper left edge of fill bar)
        E + DIC TEST FILL BAR HEIGHT mtp DIC TEST SCREEN WIDTH mtp 5;
        B = DIC TEST SCREEN WIDTH;
    "Dic Test Visualize Separator"
        [E] = 00 FFFFFFh;
        E + 1;
        B ^ Dic Test Visualize Separator;

    (-------------------------------------------------------------------------)
    (Update the screen.)
    "Dic Test Visualize Exit"
        [Display Command] = RETRACE;
        isocall;
    (-------------------------------------------------------------------------)
        leave;
    (=========================================================================)

(*****************************************************************************)
"Dic Test Draw Square"

    (=========================================================================)
    (Called from 'Dic Test Visualize')
    (-------------------------------------------------------------------------)
    (At address E draw a square of DIC TEST FILL BAR HEIGHT-4 edge length.)
        B = DIC TEST FILL BAR HEIGHT minus 4;
        E -->;                          (Need start of symbol back)
    "Dic Test Draw Square Line"
        C = DIC TEST FILL BAR HEIGHT minus 4;
        E -->;                          (Need start of line back)
    "Dic Test Draw Square Pixel"
        [E] = [dic test symbols color];
        E +;
        C ^ Dic Test Draw Square Pixel;
        <-- E;                          (Former start of line)
        E + DIC TEST SCREEN WIDTH;      (Start of next line)
        B ^ Dic Test Draw Square Line;
        <-- E;                          (Drawn symbol's start)
        leave;
    (=========================================================================)

(*****************************************************************************)
"Dic Test Clear Symbols"

    (=========================================================================)
    (Called from 'Dic Test Visualize')
    (-------------------------------------------------------------------------)
    (Starting at address E we clear all max. 9 symbols of that line. E will be
    in the starting position of the next symbol line when leaving.)
        A = DIC TEST FILL BAR HEIGHT minus 4;
    "Dic Test Visualize Clear Millions Line"
        B = DIC TEST FILL BAR HEIGHT minus 4 plus 2;
        B * 9;                          (Clear all 9 symbols)
        E -->;
    "Dic Test Visualize Clear Millions Pixel"
        [E] = 00 000000h;
        E +;
        B ^ Dic Test Visualize Clear Millions Pixel;
        <-- E;
        E + DIC TEST SCREEN WIDTH;      (Next line to clear)
        A ^ Dic Test Visualize Clear Millions Line;
    (Advance two lines to separate symbol lines from each other.)
        E + DIC TEST SCREEN WIDTH;
        E + DIC TEST SCREEN WIDTH;
        leave;
    (=========================================================================)

(*****************************************************************************)

Linoleum Syntax Highlighting produced with LSH (© 2007 by Herbert Glarner)

---