Associative Arrays / Hash Tables / Collections in SCL

I've been using QUEST for just over five years now, and over time I've become more and more bothered by its lack of a hash table data structure, like I get out of the box in VBA (I know, VBA is pretty ancient stuff itself, but compared to SCL, VBA is a dream, in my opinion.)

A hash table is a data structure is basically a string array that instead of being indexed by numbers, is essentially indexed by strings. In VBA, a hash table is called a Collection, and provides methods for adding, removing, and iterating over its contents. Most implementations of hash tables allow you to put anything in the "bucket" of stuff, keyed by a string.

The purpose of a hash table, as far as I can tell, is to provide a somewhat faster mechanism for finding items in an array than by just looking at every item one by one. Call this the slowest possible case. The fastest possible case would be to just convert a string into a big long binary number, and have a gigantic string array with enough indexes to hold any length string we can throw at it. This is probably the fastest case (I think fetching an item from an array is done in constant time), but it's not really feasible, especially with QUEST SCL, because we don't have all the memory in the world to hold this huge array, which, by the way, would be pretty much empty.

So enter the hash table. According to the Algorithms in C++ book I picked up at the library book sale for 75 cents, we can instead create a small array, with each array space holding a linked list of items with a specific hash value. The linked lists are there because we know that by limiting the size of our array, we can have different keys with the same hash.

The idea then, for searching for a key value, is that you hash the key and get a number between 1 and 111, and get the base node in the linked list at that array index. Then, we just search through each of the nodes in that linked list until we find our exact key value, and return the original string.

This kind of thing seems pretty easy to pull off with SCL, as it's just a matter of providing the hashing function (nicely included in the book), and a way to hold an array of linked lists for each of our 111 possible hash values.

I've put together a hash table utility in SCL, though I called it a collection. It's available for download here with an example for using it here. I put the hash_table.scl file into my directory of always compiled utility routines.

To use the hash table, you have to include the SCL file (I had to specify the full path to the file, so you'll have to modify that to accommodate your system. To create a collection, call the new_collection routine, which initializes a collection structure. Use col_add to add an item, remove_item_from_collection to remove an item, and col_item_exists to check if there is an item in the collection already. The kill_collection procedure will deallocate all the memory for the collection, so make sure to call that when you're done with it, or you could end up eating a lot of memory, depending on how you use this.

Another note, you can loop through every item in the collection, starting (assuming you call your collection col) and looping through a linked list of every item in the collection.

I haven't tested it terribly well, but the example file seems to work as I intend, so unless I start using it and find it broken, this is how it'll stay.

I'm not sure how much faster this is, computationally, than just looping through each item in an array and checking it. It's probably a little slower for small collections, but I imagine as the thing grows the hash table becomes faster than just looping, but I don't know. I do think it'll make some lookups a bit easier, at least from a programmer's productivity perspective, but then again, what do I know? Either way, I'll have to try and implement more of these algorithms, especially the section on regular expressions.

Labor Popups (or, Demystifying the Labor System in QUEST)

Labor logic can be really difficult to understand without first getting the proper grounding in just what's going on. I was lucky enough to get some training from Martin Barnes at DELMIA, who stepped me through the entire process, including how popups play into things.

Basically, the labor system uses a controller to select a labor to fulfill some request, then it passes information about the request through a command. The labor then picks up the command and acts on it. This seems simple enough, but reading through the code it doesn't seem so straightforward, as you can't see the labor actually doing anything. This is because of popups.

Popups in QUEST allow a user to write incredibly flexible (reusable) logics at the expense of readability. In the default labor process logic, you can see the labor just constantly sits there getting the next pending command to work on, and then does a switch block to see what kind of command it is. It then gets a handle to the popup it should use to execute the command, and runs that popup.

So in the case of laborers, a popup is simply an object that lets us run some SCL code without knowing ahead of time precisely which SCL routine/procedure to run. You just query the popup that a user has selected, and run it, and assume that logic is taking care of business.

When we apply this thinking to the labor system, it demystifies things a little bit (at least for me). The regular labor process logic then becomes fairly simplistic...do a switch against the command type, and based on command type, get a handle to the logic to run, then run that logic.

The real meat of the labor logics, and the thing that kept me from understanding how they work, is in the default popup implementations.

In the labor Logics window in QUEST, you'll see a few options beyond the regular process and init logics. These are all popups, just a way of selecting a procedure/routine that's going to get called in the default labor logics. So to see what these default selections look like, we can just look at a labor's properties and see the routine names and file paths for the selected popups. The default labor load popup is notify_after_all_loads and can be found in QUESTlib\SYSDEF\LOGICS\agv_load.scl.src.

If you load that file up in an SCL editory, you can see the notify_after_all_loads is a procedure that takes an agv_cmd handle (agv's and labors are pretty similar, you can see, by digging into their logics. My understanding is laborers were essentially copied and pasted from agv's, back in the day at Deneb. Old/ex Deneb people can be dangerously misleading, but interesting nonetheless).

The flow of this logic is much much more readable than the labor process logic, again, because this is where we actually DO stuff. So here we can see that we do load processes if necessary and all that, but eventually we just do a REQUIRE PART EXACT the_part, where the_part is just a handle passed in as cmd->part_handle.

The interesting thing about this line of code is that it's the same thing a machine element uses to get parts (or buffers, whatever). If you look at the unload popups, you see it's just transferring a part to whatever element it's at. There is nothing the least bit magical or mystifying here. In fact, this makes the labor system seem to make a lot of sense.

This may have been obvious to you, but I was never able to get a handle on this until someone walked through the whole thing with me. I know I can't do as good a job as Martin did, but I hope this gives newer QUEST users who don't know the labor system the ability to go in and see just what's going on. Ever since I "saw the light" on how this all works, I've been able to write my own labor controllers and labor logics. With that understanding comes the ability to get very detailed control of your labors, as well as the ability to write some really really bad code. Be careful.

Here's a quick example of a custom labor load popup I recently had to write. The labor would load a part and immediately destroy it, with the controller having already gotten what it needs from the part. Keep in mind I'm using a custom controller, so I don't need to notify the controller that the labor destroyed the part. Your mileage may vary.

procedure custom_labor_load_popup( cmd : Agv_Cmd )

Var

the_part : Part

Begin

the_part = cmd->part_handle

require part exact the_part

destroy( the_part )

End

Hand-Drawn Value Stream Map

Sometimes I get ideas where I can't really let go of them, until they're realized. These ideas tend to be stupid, useless, or impractical, or any combination of the three. I probably would do better to just let these things go, but to this point I've only been able to just implement the idea and move on (case in point).

Here's another stupid idea I couldn't let go of: making computer-drawn value stream maps look hand-drawn. It was a concatenation of circumstances that made me implement this; namely, I saw a post on a Visio blog on making shapes look hand drawn.

So I wrote a VBA macro in Visio that takes an eVSM map and makes it look hand drawn. I implemented this and moved on, like I feel I should. But recently, I saw a post somewhere linking to a whiteboard font based on the t.v. show House, and decided I couldn't live without seeing how it my "hand-drawn" maps would look with a "hand-drawn" font to go with it.

Here's a regular eVSM map:

And here is one of my "incredible" hand-drawn maps, rendered like on a whiteboard (minus any smudges one might expect):

I guess my point for sharing this was just to, 1, show off a really stupid little trick I somehow couldn't live without, and 2, to say that sometimes you have to just give up and give in to that part of your brain that thinks "wouldn't it be cool if...". Who knows, it may come in handy some day (and I mean the experience of working through that problem).

Winter Sim Presentation (2010)

I saw some cool presentations at Winter Sim this year. One vendor presentation that stood out for me was from forio.com, which lets you upload simulation models and run them in the cloud. Very cool.

I also gave a presentation with Swee Leong from NIST:

Bitwise Comparison

Say you want to have a routine in QUEST SCL that may have to do some things and not others, or vice versa. One way you can specify what sections of code to do is have a series of "flag" that tells the routine what to do and not do. Each flag controls one aspect of the code.

One place I can use this kind of control is in a routine for writing debugging messages to a text file, and optionally to the screen. So for one of these routines, I'd probably want a flag saying whether or not to write to the screen, and another to specify if it's an error message (in which case write to the screen and ignore the other flag), and maybe two more for telling the routine when I'm entering a routine and exiting a routine (to keep track of the call stack, so to speak).

So in this case, I'd need to have four flags I'm setting to true or false every time I call this writing routine. And, if I want to add another flag, I have to change all the calls I've made to this routine to match up with the new flag, since SCL doesn't give you the ability to add optional arguments.

So, rather than deal with this issue of having a flag variable for each option I want to add in a routine, I can instead take advantage of the nature of binary numbers in the computer. Before I continue, keep in mind that I didn't major in computer science or computer anything, so my explanation will probably sound hokey and not quite right.

A computer deals with numbers using binary, where we have a set of numerals that can have a value of zero or one. Each numeral you add on adds a power of two (rather than 10 like in our base-10 system). So, for instance, 1 in binary comes out to 2 to the power of 0, or 1. 10 in binary comes out to 0 to the power of 0 (0) plus 2 to the power of 1 (2) = 2. 100 comes out to 0^0 + 0^1 + 2 ^2 = 4. 1010 comes out to 0^0 + 1^1 + 0^2 + 2^3 = 10

Hopefully, if I did that right, you'll see a pattern where each digit we add onto the left adds another power of 2. 1 = 1, 10 =2 , 100=4, 1000=8, 10000=16, and so on. By seeing this pattern, we can also see that we could use a binary integer to store a series of yes/no flags using 1 for yes and 0 for no (or whatever you want). For instance, 2 + 8 in base 10 equals 10 + 1000 in binary or 1010.

The practical upshot of all this so far is, we can now create a series of flags, each unique flag being a power of two value (1,2,4,8,16,32, and so on), and we can store all the flag values we want to activate by adding the ones we're using together.

So, to define our constants for our message logger:

WriteToScreen 1

ErrorMsg 2

EnteringRoutine 4

ExitingRoutine 8

If we want to write that we're entering a routine we'd just pass in WriteToScreen + EnteringRoutine, which would calculate to 9 in base-10, and our routine could then know which flags to activate based on that number 9.

Now, to break that 9 back up into its parts, we need to go backwards and turn a decimal number back into binary 1's and 0's. Following is a routine that'll do that for us. I'm not sure it's the most efficient, but it seems to work. It works by reading left to right in the powers of two (starting at power 8 - you could increase it if you have more flags to handle). So it starts and sees if 2^8 (256) is less than the num we're trying to break apart. If it is, we turn that flag to true, and subtract 256 from the number until we get down to the last power. In this routine we pass in the flag we want to check against, and return true if the bit we're looking at is true.

Hopefully I didn't bungle the explanation too much, but I really just wanted to have this routine up for future reference, and hopefully it gets you thinking of ways it can help you write more concise or powerful code in SCL.

routine bitwise_or( num : Integer ; against : Integer ) : Integer

Var
 i : Integer
 pow : Integer
 sum : Integer
 result : Integer
Begin
 sum = num
 for i = 8 to 0 by -1 do
    pow = 2 ^ i
    if( sum >= pow ) then
       sum = sum - pow
       if( pow == against ) then
          result = true
          break
       endif
    endif
 endfor
 return result
End

GetTickCount

Tonight I was trying to debug some slow SCL code, and wanted to pinpoint exactly which routines were taking the longest to execute. QUEST has a systime() routine that returns the number of seconds since midnight. However, I wanted more accuracy, so I needed to use the GetTickCount routine provided by the Windows API.

I can call this routine using C_EXEC in SCL, and the final routine comes out like this:

routine get_tick_count() : Integer

Const

THE_DLL 'kernel32.dll'

THE_CMD 'GetTickCount'

Var

func_return : Integer

Begin

func_return = c_exec( THE_DLL + ":" + THE_CMD )

return func_return

End

Now, I can get a bit more visibility into what's taking my logics so long to run (though be sure to disable any calls to this routine once you're ready to just run the model)

Select a Part

The other day I was working on a project where I wanted some stats on a part in a model that don't show up in the Trace Entity window. So, I went to write a macro that would let me select a part and show the information I needed. I then realized that I didn't have a routine available that would let me easily select a part, so I went about writing one. Now, it's available for download here, because it was a pain to write and now you don't have to write it too.