Using Variant Attributes for High-Performance Lookup Tables in LabVIEW


If your instinct is to use an array to manage a lookup table, keep reading – there’s a far better way.  In case you’re not familiar with the term, a ‘lookup table’ refers to a large table of values that need to be randomly and arbitrarily retrieved programmatically – you may also see these referred to as a ‘dictionary’ or ‘map.’  As the name implies, these are typically used in software when you want to retrieve a very specific element or value from a large dataset based on some unique identifier or key.  If the data you need to retrieve is stored in a large, unsorted array, the only way to retrieve the information is to inspect every element in the array until you find the information you need – this is often referred to as a ‘brute-force’ method, and it’s highly inefficient and extremely slow.  As I’ll explain, variant-attributes provide a very efficient and highly performant alternative to this approach in LabVIEW.

A real-world scenario that may help cement this concept would be the task of looking up a word in a dictionary – the word itself is the unique identifier and the information we’re hoping to retrieve is the definition of that word. No one would ever try to find a word by inspecting every page in order, as this could take an extremely long time.  Instead, we quickly skip to the word we want thanks to the fact that the dictionary stores the word in a sorted order.  A typical dictionary (especially a print edition) also has the luxury of being a predefined dataset that remains fixed – words are not regularly added or removed.

In software, large datasets are often dynamic – elements are regularly added, changed or removed, which necessitates an efficient algorithm to easily find, retrieve, store and modify these items.  I recently published this Measurement Utility, which employs several lookup tables that I’ll use as examples.  If you’re not familiar with it, this utility is an architectural illustration of how to abstract measurements, the hardware that they measurements interact with, and the results that individual measurements return.  The framework keeps track of the measurements that are currently running, the hardware that the system has access to, results from completed measurements, and other characteristics of the system.  Since the framework is designed to run arbitrary measurements with arbitrary (but compatible) hardware, I needed a dynamic and performant way to easily store and retrieve various pieces of information.

The Measurement Utility uses a total of seven lookup tables to store various pieces of information, all of which are retrieved using a unique identifier string. If you’re interested in exploring any of these and their use, look for them in the private data of Controller Object (in user.lib). The data-type of the value returned is predefined and indicated in the parenthesis:

  • Table 1: Given the name of a measurement, return the queue to send messages to this task (Queue Reference)
  • Table 2: Given the name of a measurement, return the Object representing this measurement (Class)
  • Table 3: Given the name of a piece of hardware, return the Object representing this device (Class)
  • Table 4: Given the name of a measurement, return an array of device types (ie: DMM, FGEN) it needs (Array of Strings)
  • Table 5: Given the type of hardware needed, return an array of device IDs (ie: PXIe-4110) that match the type (Array of Strings)
  • Table 6: Given the device ID of a piece of hardware, return whether or not it is currently in use (Boolean)
  • Table 7: Given the name and time of a previously run measurement, return the Object representing the results of this measurement (Class)

Before going any further, we need to understand what a variant-attribute is.  A variant is a data-type in LabVIEW that can be used to encapsulate and store any piece of data in LabVIEW; however, nothing is actually stored in the variant when using it as a lookup table.  What we care about for the sake of creating a lookup table is a little-known property of the variant data-type: it can store attributes!  If you look under the ‘Cluster, class and variant’ palette and dig into the ‘variant’ sub-palette, you’ll see the API that we’ll use – in particular, we care about the following functions:

imageA2.png

Figure 1: The API for storing and retrieving keyed-value-pairs using Variant Attributes are straight forward and easy to use

This very simple API takes advantage of very high-performance algorithms under-the-hood to sort, manage and retrieve keyed-value-pairs.  As per usual in LabVIEW, you don’t have to know or understand how this mechanism works to take advantage of it, and it saves you the trouble of trying to keep a dataset ordered and writing the algorithms necessary to parse it efficiently (think hash tables and linked-lists).

One of the logical next questions is, ‘how much more performant is a variant-attribute table versus simple brute-force?’  The actual speed will obviously vary depending upon where in an array the data value would be located, but to compare algorithms you always examine the worst-case scenario.  The worst-case-scenario for brute force is that you’ll have to look through every single element before finding an item at the end, so we denote this as O(N) complexity, meaning that there is a linear relationship between the number of elements and the amount of time this operation may take.  Variant-attributes are implemented using a C++ std:: map structure (this has not always been the case – only in more recent versions of LabVIEW), which has an O(log N) complexity, which is a considerable difference, even as N approaches a modest size.

ImageB.png

Figure 2: A comparison of the two algorithms reveals a considerable difference between the performance – the performance of the variant-attribute table is represented by the blue line, which is very hard to see when compared with the linear complexity of an array.

In addition, it’s also much simpler than writing the code necessary to parse and search an array.  The following block diagram illustrates how Table 2 is used in the Measurement Utility to retrieve the specific object representing a measurement based on the name.

Image C.png

When loading a new measurement into the system, tables 2 and 4 are populated with information: Table 2 is the only location where the Measurement Object is stored (to avoid data copies), and Table 4 allows quick retrieval of the required hardware types when needed.  You could argue that table 4 is unnecessary, but since retrieving this information is a common operation (performed everytime a user selects a measurement from the UI drop-down), I made the design decision to not fetch the measurement object every single time.

ImageD.png

For those of you familiar with the Actor Framework, the Measurement Class is actually derived from the Actor Class.  Everytime a measurement gets spun up, the queue for this actor is stored in Table 1, which makes it easy to retrieve anytime a message needs to be sent to that measurement.  Upon completion of the measurement, that queue is deleted from the lookup table.  Results are returned (as an object) from measurements upon completion, which are stored in yet another lookup table (Table 7).  This is especially useful, since we can easily accrue a large number of results, and we want  users to be able to quickly retrieve and review results.

Hopefully this gives you a good understanding of how variant-attributes can be used as a much more efficient alternative to arrays.  If you’re interested in learning more, I would encourage you to explore the Measurement Utility referenced by this article, here. As usual, let me know if you have any thoughts or feedback or want additional explination!

Advertisements

4 thoughts on “Using Variant Attributes for High-Performance Lookup Tables in LabVIEW

  1. Great write-up on Variant Attribute Databases! Two thoughts: Get Variant Attribute does not necessarily need to be followed by Variant to Data for type conversion; you can wire the object constant directly into Get Variant Attribute into the “default value” terminal (that’s for Image+C.png above). Since Get Variant Attribute does not return an error if the attribute is not found, the atomicity of two functions does not gain functionality (except for the crystal-clarity of a well-demonstrated blog post ;-). Also, I notice you’re using a read-mod-write pattern on variant attributes, so go vote for kegghead’s idea about IPE support for Variant Attributes! This would provide a data mutex, and is also more beautiful syntactically. (Here’s the link: http://forums.ni.com/t5/LabVIEW-Idea-Exchange/In-Place-Element-Structure-Support-for-Variant-Attributes/idi-p/1391396).

  2. Pingback: Designing a LabVIEW Measurement System with Multiple Abstraction Layers | Software Engineering for LabVIEW

  3. Pingback: Quick look up !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s