Huge Lookup Lists in SPIN

Rumple

I'd like to implement a lookup list with an absurd number of expressions (2048, to be exact). I'm having trouble fitting the comma-delimited expression list (in hex) on one line in the editor...and it doesn't like it when I try to spread it over multiple lines.

I was wondering if anyone knew how to either spread the list over more than one line or how to define the list somewhere and "import" it into the LOOKUP command.

Should I use a huge CASE block instead? While playing with smaller lists, I've noted that LOOKUP generates much more compact code than CASE. I figured LOOKUP stands a chance of being faster, but I may be wrong.

Thanks.

kuroneko

So is it in fact a list (you mentioned hex)? Then something like this may help:

DAT font word {

}$0000, $0000, $0000, $0000, $0550, $0550, $5555, $5555, $0010, $0000, $0000, $0000, $0140, $0140, $0000, $0140,{
}$0000, $0140, $0140, $0140, $0140, $0000, $1414, $1414, $1111, $0055, $0055, $0055, $0055, $0000, $0000, $0000,{
...
}$5541, $0155, $5555, $5555, $5555, $5555, $5555, $5555, $5555, $5005, $5555, $5555, $5555, $5555, $5555, $5555

Access then simply by font[idx]. Note that with a lookup[z] which is filled with expressions each of them is evaluated until it finds a match or end of list. This is expensive in terms of runtime.

Rumple

Thanks for the reply, K.

Do you know whether or not that's the case with the CASE command too?

kuroneko

Rumple wrote: »

Do you know whether or not that's the case with the CASE command too?

Well, it has to evaluate the expression(s) to figure out whether it matches. Single values are easy, everything more complicated takes time. Evaluation is top down, IOW, if the last entry is the one you want it's the slowest lookup/case.

Can you give an example of what your expressions look like?

Mike Green

The same issue comes up with CASE statements as well. It's not efficient to have a huge number of cases. That's not what these statements are for.

JonnyMac

I'm with Marko and Mike: use a DAT block for a very large table, and your own logic to determine to correct index into that table.

When storing the elements of a table it is not necessary to extend one line. The style shown below is easier, I believe, and helps one re-arrange small groups within the table (if they exist).

dat

  LongList      word    $0000, $0000, $0000, $0000, $0550, $0550, $5555, $5555 
                word    $0000, $0000, $0000, $0000, $0011, $0011, $0011, $0011

Dave Hein

If your expressions are just numbers you can do what kuroneko suggested, except I would break it up into multiple lines, such as

DAT

font word
  word $0000, $0000, $0000, $0000, $0550, $0550, $5555, $5555, $0010, $0000, $0000, $0000, $0140, $0140, $0000, $0140
  word $0000, $0140, $0140, $0140, $0140, $0000, $1414, $1414, $1111, $0055, $0055, $0055, $0055, $0000, $0000, $0000
...
  word $5541, $0155, $5555, $5555, $5555, $5555, $5555, $5555, $5555, $5005, $5555, $5555, $5555, $5555, $5555, $5555

If your expressions are more complicated than just a list of numbers I would break it up into multiple nested CASE or LOOKUPZ statements. This will be more efficient, and it gets around the limitation on the number of expressions you can have with CASE or LOOKUPZ statements.

EDIT: Jon (AKA JonnyMac) posted the same idea of breaking up the list into multiple lines while I was composing my post.

Rumple

I'm building a simple data converter - 11 parallel bits in, 12 parallel bits out, with no logical or mathematical correlation (that I can see, anyway).

The SPIN line that does the work looks like this:

outa[12..23]:=lookup(ina[0..11]:$1A1,$177,$A21,$A12,$B60,$717,$550,$02A,...on and on and on...)

So far. I haven't actually run any code yet, just seeing what compiles.

The project is still in the "playing with ideas" stage, so I'm certainly willing to listen to alternative methods if anyone would like to contribute one..

Thanks again.

JonnyMac

What the responses have in common is the notion that if you think you can do it with LOOKUP or CASE, you can do it with a DAT table, too.

idx := ina[IMSB..ILSB]

  if ((idx => LO_LIMIT) and (idx =< HI_LIMIT))
    outa[OMSB..OLSB] := LongList[idx]
  else
    outa[OMSB..OLSB] := $0000

Mike G

I'd look at sorting the values and using a binary search.

LoopyByteloose

Rumple wrote: »

I'd like to implement a lookup list with an absurd number of expressions (2048, to be exact). I'm having trouble fitting the comma-delimited expression list (in hex) on one line in the editor...and it doesn't like it when I try to spread it over multiple lines.

I was wondering if anyone knew how to either spread the list over more than one line or how to define the list somewhere and "import" it into the LOOKUP command.

Should I use a huge CASE block instead? While playing with smaller lists, I've noted that LOOKUP generates much more compact code than CASE. I figured LOOKUP stands a chance of being faster, but I may be wrong.

Thanks.

You might try downloading a FREE text editor for generic computer work. I use Gedit and it is available both for Linux and Windows. I transfered the DATA from a spreadsheet to clean it up.

++++++++++++++++++++++++++++++
I did exactly what you desire to do in pfth Forth on the Propeller and the problem is hidden white space characters. Gedit will allow you to see and remove them with a FIND and REPLACE. Even an extra normal space may cause trouble in some instances.

2048 items is no problem at all. I just used CUT and PASTE and made sure that everything was using ASCII (not UTF-8 or UTF-16). Stay with LOOKUP for a position search as CASE is testing each character with a true or false.

With DATA, you can do other searches that are faster if you put all 2048 items in a simple ARRAY and if they are all numbers they can be represented as binary Longs, signed or unsigned.

++++++++++++++++++++++++++
Sorting adds a whole additional aspect to what you desire. What kind of sort are you considering?

I pre-sorted all my DATA in a spreadsheet and then just copied the list that was in the order I required. This makes using the data extremely fast.

Dave Hein

The most efficient way to do this is with a lookup table. It will be faster and take less space than using either LOOKUP or CASE. The code for using a lookup table would look like this:

DAT
table word
  word $1A1,$177,$A21,$A12,$B60,$717,$550,$02A
  word ...
...
PUB ...
  ...
  outa[12..23] := table[ina[0..11]]

I'm assuming the first entry of $1A1 is for an input of 0. If it is really for an input of 1 like your sample code implies then you need to add the value for an input of 0 to the table.

EDIT: BTW, ina[0..11] is the bit-reversed form of ina[11..0]. Is that what you really want? Maybe you just need to use the non-bit-reversed form.

Rumple

Thanks for the replies, guys. When that project gets green-lighted I'll go with the DAT table method.

But...FWIW, I did manage to hunt down the answer to my original inquiry which was "how do you spread a command over multiple lines?".

Here's Phil Pilgrim in a 5-year-old thread:

"To continue a line, put a { at the end and a } at the beginning of the continuation line. This effectively comments out the terminating carriage return. (I can't take credit for this trick, but I also can't remember who first came up with it.)"

This method does indeed work with LOOKUP command. Cool.

kwinn

Simpler and much faster to use the 11 bit input as an offset into a table of words that contain the 12 bit output you want. So 12bitOut = Table[11bitIn]

Rumple wrote: »

I'm building a simple data converter - 11 parallel bits in, 12 parallel bits out, with no logical or mathematical correlation (that I can see, anyway).

The SPIN line that does the work looks like this:

outa[12..23]:=lookup(ina[0..11]:$1A1,$177,$A21,$A12,$B60,$717,$550,$02A,...on and on and on...)

So far. I haven't actually run any code yet, just seeing what compiles.

The project is still in the "playing with ideas" stage, so I'm certainly willing to listen to alternative methods if anyone would like to contribute one..

Thanks again.