Is there a way to programatically create a variable in Spin?

sccoupe

Lets say that I have data incoming on the serial port that has a header ID followed by a set number of data bytes. I want to store that data in a variable named as the header. Even given thought to hooking up an external serial ram or something to just use the header a memory address. Any thoughts or ideas on this?

Thanks

MagIO2

Variables are only for the programmers convenience and are resolved by the compiler to memory addresses. For a propeller I would say it is overkill to implement some dynamic memory management which additionally uses a name to memory address mapping.

How fast is the data coming? Maybe it would be a solution to store it on a SD card, where the filename equals the header ID?

What is the lifetime of the data? How is it used later on?

sccoupe

Data will come in at 115k. I'd prefer not to use an SD card because of the number of constant writes involved. Data lifetime will be until the device is shutdown. The data will then be accessed by a much slower serial port, say 300 baud. The idea is to keep the most updated info available for a slower bus for when it is requested. It may request variable A once per second and variable B, 4 times per second, but its all coming into the 115k stream at 10 times per second for example.

Phil Pilgrim (PhiPi)

What's the maximum number of characters a variable name can contain? How many different variable names are there? From what you're describing, it sounds like a hash table would do the job.

-Phil

MagIO2

Does the size of one "variable" change over time? What is the max. size? How many different variables do we talk about?

sccoupe

The headers are always two bytes and ALL header values will never be used but must be ready for anything. The header is always followed by 8 data bytes. These are strict lengths, so always 10 bytes with header and data.

Phil Pilgrim (PhiPi)

In the course of one power-up, how many different variable names do you expect to encounter?

-Phil

sccoupe

The max would be 2000, but realistically I'd only see maybe 100.

Phil Pilgrim (PhiPi)

What are the allowable characters in a variable name?

-Phil

jazzed

Two byte header and fixed sized data certainly makes the problem easier ... as long as that specification never changes.

That should be easy to manage in N different files. Obviously one file of 64K headers can't be read and manipulated all at once by Propeller memory.

sccoupe

All characters are possible. They are not meant to be human readable and are received as a 16 bit number. So the headerr would be anything from 0 to 65535, but come across the serial port as hex I guess. 0x0000 to 0xFFFF.

sccoupe

I was kind of thinking that if I have 2 header bytes and 8 data bytes, I could store the first 200 variables in ram, using only 2k. I'm just not sure how to go about storing in a way that I can go back and find it correctly.

Heater.

Sounds like you need a hash table or other "key value store" object, perhaps a linked list of key-values. Surely someone has made such a thing in the long history of Spin.

As a minimum you could create an object that maintains two simple arrays. One is a list of IDs received, the other is a list of pointers to the byte data.

It would have methods like:

put (id, dataPtr)

get (id)

Phil Pilgrim (PhiPi)

Each entry requires 10 bytes. 2048 entries would take up 20_480 bytes, leaving more than 12_000 bytes for your program. If the program is as simple as you seem to indicate, this should not be a problem. What remains is to create a hash function to map $0000 - $FFFF to $0000 - $07FF. If the distribution of possible keys is uniform, just about any hash function would do, including ignoring the first five bits, and using the lower 11 bits to index the arrays of keys and values. In case of a collision (i.e. two keys mapping to the same location), just increment the index until you find an empty slot. On the retrieving end, you'd use the same hash function to map into the table of keys, then increment the index, if necessary, until you find a match. Then access the corresponding entry in the values table.

If the distribution of possible keys is non-uniform, then the hash function may require a little more work if you want to minimize the number of collisions, thus speeding up writes and reads.

-Phil

kwinn

A simple although somewhat brute force approach would be to use a 1MB external memory to hold the data.
The 16 bit ID would be used as the address of a pointer that points to the actual location of the data.

Very fast, but not very memory efficient.

An even faster alternative would be to use the ID as the address of the data by shifting it left 4 bits.

sccoupe

So something like...

Define variables: VariableID[2000]
LastUsedLocation := 0xMemory Location

When data received: If VariableID[Header] = zero
VariableID[Header] = LastUsedLocation + 8 (8 data bytes)
Store the 8 bytes of data there
LastUsedLocation = LastUsedLocation + 8
else
Store the 8 bytes of data at memory location 0xVariableID[Header]

sccoupe

kwinn wrote: »

A simple although somewhat brute force approach would be to use a 1MB external memory to hold the data.
The 16 bit ID would be used as the address of a pointer that points to the actual location of the data.

Very fast, but not very memory efficient.

I like this option too. If the memory is of a ram type, cheap and accessed as easily as a serial eeprom, the coding should be real easy. I guess in this case it would be HeaderID is memory location for byte one, byte two is at memory location HeaderID*2, etc.

MagIO2

I would not hash .... I'd simply organize the memory as a sorted list. The header comes first and is the sort criteria. With a binary search you can find each entry with a few compares. The longmove should be fast enough to insert a new variable in the middle.

Phil Pilgrim (PhiPi)

I think you should not be afraid to try the hashing approach. It's much quicker than a linear search for data retrieval and would not require any external memory. Plus, once an item is placed in memory, it never has to be moved, as it would with a sorted list.

BTW, a binary search in a 2048-entry table can require as many as 11 compares. A properly-crafted hash function could entail far fewer than that.

-Phil

kwinn

Your reply was too fast for me. Look at the addition to my previous post. Coding would be even simpler.

Heater.

How on earth is adding external RAM to your hardware and it's drivers to your software the "simple" approach?

As Prop programmers our minds should reel at such waste.

It can be done with a simple arrays of ID's and data. Even the brute force linear searching and subsequent insertion into those arrays would do fine.

If performance is an issue we can look at hash tables or whatever.

sccoupe

MagIO2 wrote: »

I would not hash .... I'd simply organize the memory as a sorted list. The header comes first and is the sort criteria. With a binary search you can find each entry with a few compares. The longmove should be fast enough to insert a new variable in the middle.

So, your saying when the first data comes in, write the 10 bytes (header and data) to the first memory location. When the next byte comes in, compare the header ID with each header ID in memory until it comes to an ID that is higher and them move everything from that location up 10 bytes and drop the new data in the hole? We end up with a lump of data that is ordered numerically from low ID to high ID. This sounds the most efficient and cheapest. Moving the data around may be a bit sluggish, but after all ID's are sent once, then there is no more moving of data, just replacing.

kwinn

Boy you guys are fast posters. Using an external memory and the ID x 16 as the address makes for very fast and simple storage and lookup. With a 4 bit counter in addition to the 16 bit register for the ID the code would be trivial.

kwinn

Heater. wrote: »

How on earth is adding external RAM to your hardware and it's drivers to your software the "simple" approach?

As Prop programmers our minds should reel at such waste.

It can be done with a simple arrays of ID's and data. Even the brute force linear searching and subsequent insertion into those arrays would do fine.

If performance is an issue we can look at hash tables or whatever.

Good point provided all the data will fit in hub ram, however if external memory has to be added it might as well be done to make the software and coding as fast and simple as possible.

jazzed

A linear array is fine until the list gets too big.

I wrote a hash table in spin once. I just can't find it

I found this in C though: http://forums.parallax.com/attachment.php?attachmentid=93461&d=1339511663
Change to CMM mode and replace printf, etc... with simpletext library functions for a much smaller implementation.

Phil Pilgrim (PhiPi)

Here's a simple hashing scheme, including the insert and retrieve functions. It assumes that all keys are equally-probable but that the key $0000 is not allowed.

CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

VAR

  word keys[2048]
  byte values[2048 * 8] 

PUB  start

  '' Main program.

PUB insert(key, value_pointer)

  '' Insert an 8-byte value pointed to by value_pointer into a table indexed by key.

  bytemove(@values[hash(key) << 3], value_pointer, 8)

PUB retrieve(key)

  '' Retrieve the address of an 8-bit value in the table indexed by key.

  return @values + (hash(key) << 3)

PUB hash(key) : index

  '' Get the index into the keys table that matches key. If no entry exists, create one.

  index := (key & 2047)
  repeat while (keys[index] and keys[index] <> key)
    index := (index + 1) & 2047
  keys[index] := key

-Phil

MagIO2

For a first iteration you can sequentially search for the keys ... a later improvement would be to use binary search which needs much less comparisons. For 3 values it needs max. 2 comparisons, for 5 values it needs max. 3 comparisons ... 9->4, 17->5 ... 2049->12.
The longmove is totally done in PASM and is really fast .. it'll easily move MBs per second.

And yes, after data is settled there will be no more moves.

Well ... it's not the most efficient in terms of speed, as hashing would be faster if the memory allocated is big enough to avoid chained rehashes.

jazzed

Phil Pilgrim (PhiPi) wrote: »

Here's a simple hashing scheme, including the insert and retrieve functions. It assumes that all keys are equally-probable but that the key $0000 is not allowed.

Nice work Phil.

How would you characterize the insert/search performance of that? Certainly not O(1).

Although given the circumstances, the performance is not as important as the code cost.

Heater.

First order of the day is to get the thing working at all. Simple arrays with brute force linear search and insertion will do fine for that.
Then if performance is an issue think about hashes or binary searches etc.
However avoid linked lists, they are always slower.

Avoid premature optimization bla bla...

Phil Pilgrim (PhiPi)

In my example, I forgot the array wraparound. That's been fixed. Also, if insert and retrieve are called from different cogs, retrieve should use a bytemove to a provided address, and the two bytemoves should be surrounded by locking. This will prevent partial mixed values (old and new) from being retrieved.

'Just got back from a bike ride. Once I shower, I'll update my example to include the locking.

heater wrote:

Simple arrays with brute force linear search and insertion will do fine for that.

I would submit that my hashing example is simpler still.

-Phil

Phil Pilgrim (PhiPi)

Here's a multiprocess-safe example of hashing (untested, BTW). I've fleshed it out a little to demonstrate the interaction with serial I/O.

CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

  BUF_SIZE      = 2048          'Must be a power of 2.

VAR

  long stack[30]
  word keys[BUF_SIZE]
  byte values[BUF_SIZE * 8], rcv_buf[8], xmt_buf[8]
  byte lock

OBJ

  xmt : "FullDuplexSerial"
  rcv : "FullDuplexSerial" 

PUB  start

  '' Main program.
  lock := locknew
  cognew(receiver, @stack)
  repeat
    ' Do xmt stuff, calling xmt_record.

PUB receiver

  repeat
    ' Synchronize and call rcv_record

PUB rcv_record : key | i

  key := rcv.rx | rcv.rx << 8
  repeat i from 0 to 7
    rcv_buf[i] := rcv.rx
  insert(key, @rcv_buf)

PUB xmt_record(key) | i

  xmt.tx(key)
  xmt.tx(key >> 8)
  retrieve(key, @xmt_buf)
  repeat i from 0 to 7
    xmt.tx(xmt_buf[i])

PUB insert(key, value_pointer) | index

  '' Insert an 8-byte value pointed to by value_pointer into a table indexed by key.

  index := hash(key) << 3
  repeat while lockset(lock)
  bytemove(@values[index], value_pointer, 8)
  lockclr(lock)

PUB retrieve(key, value_pointer) | index

  '' Retrieve the 8-byte value in the table indexed by key.

  index := hash(key) << 3
  repeat while lockset(lock)
  bytemove(value_pointer, @values[index], 8)
  lockclr(lock)

PUB hash(key) : index

  '' Get the index into the keys table that matches key. If no entry exists, create one.

  index := (key & constant(BUF_SIZE - 1))
  repeat while (keys[index] and keys[index] <> key)
    index := (index + 1) & constant(BUF_SIZE - 1)
  keys[index] := key

-Phil