[CR] Pointer System

[bsvingen]

File Name: Pointer System

File Submitter: bsvingen

File Submitted: 18 Sep 2006

File Updated: 29 Sep 2006

File Category: LabVIEW OOP (GOOP)

Pointer System V1.1.2

Author:

bsvingen - Bjornar Svingen

bjornar.svingen@ktv.no

Distribution:

This code was downloaded from:

http://forums.lavag.org/index.php?automodule=downloads

Description:

A set of VIs that creates and controls pointer-data pairs. The basic idea is to simulate random access memory and malloc()/free() by using one single LV2 style global. The data type must specified in "..\Pointer\Data Typedef\Data Typedef__P.vi", or it can be replaced with an LVOOP class for LV 8.2. The only restriction to the number of references is the physical memory on the computer. The global stores data in an Array and uses a separate Bool Array to control access and free/protect the data.

The "address" to the data is returned directly with no type conversion (int32). Basicly the LV2 global takes data as input, put the data in an array within the global and returns the index where the data is set. This index therefore becomes a pointer to the data, and can be used later to set and get data.

The upper 8 bits of the pointer is used as a counter that is incremented by one for each new "dispose pointer" call. The "Get" and "Set" function checks these 8 bits in the pointer with corresponding counter array and throws an error if they are not equal. By doing this an error is thrown when trying to use a disposed pointer. Thanks to JFM for the counter code.

Due to the inherent effectiveness of LV2 style globals and no type conversions, this method is twice as efficient as using queue primitives, see examples provided. Functions such as New, Get, Set etc can be found in the ..\Pointer folder. A project file is also provided for LV 8.x. A more general system that takes arbitrary types is called General Reference System and can be found on this Code repository.

In contrast to queues that can be regarded as synchronous references to data, this reference system is fully asynchronous.

Allocation and freeing of data is done dynamically.

Allthough this pointer system may at first glance have some resemblence to "classic" GOOP, it is by no means a GOOP system. This pointer system is best regarded as a normal LV2 global, but with the difference that it returns a pointer (index) to the data, and therefore can be used for an arbitrary number of data.

All the VIs in the library are documented.

Support:

If you have any problems with this code or want to suggest features:

http://forums.lavag.org/index.php?showtopic=4131

Version History:

1.1.2

Fixed "dispose pointer" and "obtain pointer from pointer". Some other small fixes.

1.1.1

Updated the counter so it will increment at each "dispose pointer" instead of "obtain pointer".

1.1.0

Updated the pointers so that the upper 8 bits is uses as a counter. Using a disposed pointer will therefore create an error. Thanks to JFM.

Updated the allocation routine so 100 elements are added in one chunk. Thanks to JFM.

1.0.1

Updated this readme.txt file

Fixed a bug in "Obtain P from P" function in the global.

Added a placeholder VI (for easier conversion to LV7)

1.0.0:

Initial release of the code.

License:

Creative Commons Attribution 2.5 License

Click here to download this file

[crelf]

A set of VIs that creates and controls pointer-data pairs. The basic idea is to simulate random access memory and malloc()/free() by using one single LV2 style global.

:thumbup: That's a pretty neat implementation - have you considered creating a variant version so each of the "memory" spaces can have different structures? Also, have you considered using a string-based reference (so you can name a memory space if you want to, or just have an automatically generated name if not) rather than an integer-based reference to allow subsequent calls to reference a memoery space by name?

[bsvingen]

:thumbup: That's a pretty neat implementation - have you considered creating a variant version so each of the "memory" spaces can have different structures? Also, have you considered using a string-based reference (so you can name a memory space if you want to, or just have an automatically generated name if not) rather than an integer-based reference to allow subsequent calls to reference a memoery space by name?

I have made a variant version earlier, it can be found here. It is only for LV8.2 since it also uses LVOOP as a class for the reference. This pointer version is really only a stripped down version of the variant ref, with the aim of making references to data as efficient as possible.

I have done some (very preliminary) thoughts about using names. So far I just can't see how this can be done without adding a lot of overhead and difficulties. It will require a lookup table of some sort to be efficient (hash table or binary tree). The only primitives i know that has efficient lookup tables built in is queues and variant attributes, and i therefore think that such a system would have to include either one of those primitives built into the LV2 global or instead of the LV2 global (maybe some sort of dqGOOP style system that i have seen examples of here on the board). Either way, a lot of overhead is added when using names, since that name needs to be "dechiphered" in some way no matter how you look at it.

Probably? the most efficient way to use naming as the "reference", and if you are not too concerned about actually obtaining a "wireable" reference, is to put one single Variant in a LV2 global and set all your data as attributes in the Variant. Then you have named globals that can take any type. I have tested the variant attributes as a lookup table, and it is incredible efficient.

[Aristos Queue]

Either way, a lot of overhead is added when using names, since that name needs to be "dechiphered" in some way no matter how you look at it.

It's not that expensive if you use a dual system the way queues do of lookup normally using the number and only occassionally using the string. Only the Obtain Queue uses string. The others all do numeric lookup using the refnum. Add a function that translates string to "pointer" to your system and you're good to go.

[Mellroth]

Hi,

I think there is a "bug" in that pointer implementation.

The problem is that pointers are generated by finding the next free index. This means that if you dispose pointer p and directly obtains a new pointer q, p and q might be the same pointer value. Dereferencing the disposed pointer p would then still be possible, and would return the value from pointer q.

Please see the attached *.llb.

/J

Download File:post-5958-1158762581.zip

[bsvingen]

Hi,

I think there is a "bug" in that pointer implementation.

The problem is that pointers are generated by finding the next free index. This means that if you dispose pointer p and directly obtains a new pointer q, p and q might be the same pointer value. Dereferencing the disposed pointer p would then still be possible, and would return the value from pointer q.

Please see the attached *.llb.

/J

Good catch However, IMO it is not a bug, but simply a natural feature of pointers. It is best to think of the LV2 global as a block of Random Access Memory (RAM). The LV2 global does in fact simulate a block of RAM, and the pointer is just an int32, an address to an arbitrary place in the RAM. There is no connection what so ever between the data stored in the address and the pointer that has this address as a value, other than the fact that the data happends to be stored at the location that the pointer points to.

What happends in your example is that you allocate one slot in RAM and receives a pointer (the address) to that slot. Then you get the data, AND you copy the pointer (the address) by branching the wire. Then you dispose the data and the pointer. However, disposing a pointer means only that it does not anymore (neccesarily) point to the data that it first was set to point to. In the implementation it means that the data the pointer is pointing to is destroyd, but it does not mean that the location in RAM (the address) is destroyd, just as physical ram is not destroyd.

Since you have disposed the pointer/data relationship, it is now possible to allocate that address again and put other data into it. So your second pointer now has the same address as the first pointer, and the value they are pointing to must of cource be identical.

The same thing will happen in any other language that support pointers when you copy pointer.

It's not that expensive if you use a dual system the way queues do of lookup normally using the number and only occassionally using the string. Only the Obtain Queue uses string. The others all do numeric lookup using the refnum. Add a function that translates string to "pointer" to your system and you're good to go.

of cource. It is strange how sometimes the obvious solution just does not occur

[bsvingen]

JFM, I think maybe my documentation and naming is a bit uncorrect, and certainly the name "General Reference System" that i have used for the other LV8.2 general system using variants. The system is a pointer system (in a simulated sort of way ), and not a reference system. References in LabVIEW are completely different from ordinary pointers, and therefore it is wrong to call these pointers for references. References in LabVIEW are more like pointers to LV objects (controls, VIs etc), and sometimes they are more like pointers to pointers of LV objects (I don't know if they actually are pointer to pointers, but queue refs seems to act that way).

[Mellroth]

Even though you are correct in that it is a natural feature of pointers, I still think it is an important aspect as we work with wires in LabVIEW instead of variables. Basically since each fork copies the pointer value.

Each time we try to de-reference a pointer I would like to know whether it is the correct data (in the current implementation you can actually return data, empty, of a disposed pointer without any error).

Compare to C

If you in create a variable in C and gets the associated pointer/memory address, that pointer will always refer to the same value as long as the variable is valid. When the variable is no longer valid, it is not likely that the next variable will reuse the same memory address, and acting on a pointer that is not valid might lead to a crash.

To get around this you could let the highest byte in the pointer be a counter (wrapping at 256), indicating usage order. Check the pointer against this usage counter, and you will not see the same pointer value in 256 turns. Or use I64 values as pointer value, then use the I32-high as the counter and the I32-low as the pointer value.

/J

[bsvingen]

I think maybe i understand what you mean. But IMO a pointer is just an integer with a value of an address in memory. When you dispose a pointer, and then decides to use it later, this is bug done by the programmer, and a very serious one. I agree that it is easy to do such an error, but that is just the way it is.

Lets see the alternatives (just on top of my head):

The first alternative is to use pointers to pointers to data, then you can invalidate the pointer at the same time as you dispose of the data. ie when you invalidate a pointer one place, it will be invalidated all places.

A "New" function would then create a pointer that points to a pointer that has the value of -1 (or NIL). When you set data, the second pointer gets the address of the data. Then when you dispose, you free the data array index and set the second pointer to -1 again. In your example the "get data" of the disposed pointer would return an error (invalid pointer), since it will point to -1. Still, this would not be foolproof since you still can call (by accident) the disposed copyed pointer before you actually dispose it (there is no requirement to wire the error wire). Anyway, when using pointers to pointers i see that your solution would be quite meaningful, but it would not be foolprof, using a disposed pointer is still a programming bug.

The second alternative is that by brancing a wire with a reference, you also create a copy of the data that is referenced to. This will be a call by value approach, and is what happends when you branch an Array, but this is not what i want, and would be meaningless to do since i would not get a reference.

The third alternative would be NOT to dispose the data, but simply end the wire (no throughput). This would actually work, but with the risk of filling up the memory.

Anyway, i kind of like the pointer to pointer approach, although i'm not sure if it actually would work (how to dispose the second pointer for instance? You would probably need two functions: dispose data and dispose pointer ?, i don't know).

[Mellroth]

I agree on that its is a serious programming error, but I do not see why we shouldn't try to protect the programmer from doing such mistakes.

If you should use the upper 8bit value as a counter, the user is more or less protected.

The only drawback is that it will take another 8bit of memory for each pointer storage, and also some additional checks to see if pointer is valid.

I'll see if I can dig up some old stuff that will add that counter to your implementation, if I got time that is...

[bsvingen]

I agree on that its is a serious programming error, but I do not see why we shouldn't try to protect the programmer from doing such mistakes.

If you should use the upper 8bit value as a counter, the user is more or less protected.

The only drawback is that it will take another 8bit of memory for each pointer storage, and also some additional checks to see if pointer is valid.

I'll see if I can dig up some old stuff that will add that counter to your implementation, if I got time that is...

OK, thanks I was thinking mostly in terms of efficiency and simplicity, but i'm looking forward to see your implementation. (i must admit i am still not quite sure how the counter is to be implemented, will that be used instead of the BOOL array?)

[Yair]

Nice, although I'm not sure if this would be useful in my programs.

One point is that to shave an extra couple of microseconds you should move the Data Out terminal out of the case structure (you can just set the other cases and the error case to default data). I guess that if LV sees that the original wire is not going anywhere else it can reuse the buffer (since its the same type) and not allocate more memory.

[Mellroth]

Counter is now included in the Global Storage__P.vi

This limits the heap size to 2^24 (24bits), but in practice I do not think that this should be a problem.

I also updated the part where heap is increased so that 100 additional free elements is added together with the new element.

/J

Download File:post-5958-1158902910.zip

[bsvingen]

:thumbup: Thanks alot. That was actually pretty neat and i can't see any performance penalty either. This will be included in the update.

[Mellroth]

Looking forward to the update.

/J

:thumbup: Thanks alot. That was actually pretty neat and i can't see any performance penalty either. This will be included in the update.

[bsvingen]

The update is already there

[Aristos Queue]

nevermind

[bsvingen]

I just noticed that the "bug" is still there in some circumstances. The counter is only updated when using "Obtain pointer". This makes it possible to use a disposed pointer without an error if the get/set methods are used before obtain new pointer. I think this can be fixed by updating the pointer when disposing the pointer.

[Mellroth]

I think this is another bug. To solve this it might be enough to add a check of the "Free" boolean in the get/set cases.

The bug I was aiming at was that a reused pointer could cause strange errors. This bug also still exist, since the counter will wrap at 256.

Using 64 bit values as pointers, and 32 bits as counter will get the wrap number up to 2^32.

/J

I just noticed that the "bug" is still there in some circumstances. The counter is only updated when using "Obtain pointer". This makes it possible to use a disposed pointer without an error if the get/set methods are used before obtain new pointer. I think this can be fixed by updating the pointer when disposing the pointer.

[Mellroth]

I just quickly checked v1.1.1 and I realized that dispose and obtain_p_from_p needs to be updated.

These cases does not retrieve the array index correctly. Dispose uses correct index on counter array, but not on data and boolean array.

Maybe also add a check that the boolean element is set to true in all cases where data is accessed?

/J

[bsvingen]

Strange. I thought i had fixed that. Maybe it was OK before the fix

Edit: It's fixed now (only use get/set myself ).

[LAVA 1.0 Content]

Hi besvingen,

I had time to take first deeper look at your code. The idea looks cool and the implementation is pretty efficient. I've a few comments that I think should be considered. First when you dispose your pointers, I think you should store these disposed pointers into an array. This way when you need a new pointer, you could just pick the last disposed pointer from the array. As with heap, the array should be initialized to some default value to avoid resizing. I thinkg this will increase random-access performance.

Which leads us to the second comment. Your performance measurement wasn't about random access but about create, set, get, destroy in a sequence. So you don't really measure random access performance i.e. the case when you create and dispose pointers in random order. Now you first create all pointers and then dispose all pointers. That's not what happens in a normal programming environment. Also you should do much more get and set operations per each creation and destruction for the performance measurement to be more realistic. You always use your pointer for many operations in reality rather than dispose it almost immediately.

Third issue is related to concurrency. Your pointer system doesn't seem to have concurrency control other than the fact that only one thread can access the VI at a time. This however is not enough in most of the cases. You'll rather have a sequence get - modify - set. Your system allows data corruption in such scenratio where two threads allow to get - modify - set the same data simultaneously. The queue has a built-in locking mechanism that protects against this issue.

Fourth comment relates to performance in concurrent situations. It's not evident to me that this system performs as well as it does now if there are concurrent access to the stack. Queues only keep a lock to a single instance of data. This mechanism locks the whole stack when ever any thread tries to access the stack. This means that the stack scales less efficiently compared to queues when the number of acquired pointers increases in non-sequential system.

Overall, a very nice idea though I don't want to sound negative, these are just things that came into my mind and I think it may help to develop the concept if I share these ideas.

[bsvingen]

Thanks for the comments. About random access performance: All this is, is an array inside a while loop. To access an array requires O(1) operations no matter how long it is, or no matter which index you try to access. The only thing that takes time is to allocate new elements, or more precisely to increase the array. Array performance in LabVIEW is pretty good in general and this is precisely why the performance of this system is so good as it is. The bool array is only used in allocating and freeing, not in get/set. But of cource, a random access test would be nice and more precise and to the point.

About concurrency: If what you are saying is true, then all sub VI's in LabVIEW are ticking bombs just waiting to create disaster. So - I just don't buy it, sorry (I'm not saying you are wrong, but if calling a function, a sub VI, is not safe, then what is?). You must also remember that this system is totally asynchronous while queues MUST be synchronous to function properly.

I see it like this: It's an ordinary LV2 global with an array, and will perform just like any other LV2 global with arrays. About concurrency and stacks, I really don't know how to test this, can it be tested?

[LAVA 1.0 Content]

Thanks for the comments. About random access performance: All this is, is an array inside a while loop. To access an array requires O(1) operations no matter how long it is, or no matter which index you try to access.

My sentence was not the best possible. I didn't really refer to random access of get and set operations but to create and dispose operations in random order. There is this search array which performs probably O(N) so in natural system the creation will scale O(N) over the number of pointers in the system. You can decrease this to O(1) by keeping track of disposed pointer indeces in the boolean array. For small arrays this could however be slower.

About concurrency: If what you are saying is true, then all sub VI's in LabVIEW are ticking bombs just waiting to create disaster. So - I just don't buy it, sorry

Perhaps you understood me wrong. When user calls the Get Data operation, he gets the content of the stack but the data stays also in the stack. If the user wants to modify the data in the stack, he/she needs to get the data using Get Data, then modify it outside your VIs, and then write it back. During this time some other VI may try to do the same thing. So you get exactly the same kind of competition as you get with multiple threads in a conventional programming language. However, in conventional language you can easily control the number of concurrent threads but in LabVIEW you cannot. So to guarantee that the data doesn't change when a VI is modifying the data, it needs to acquire a semaphore to the data. That is to build a complete system you also need to create a semaphore system that blocks the access to specific pointer when another thread has acquited a semaphore for the same pointer. To build a semaphore system you either have to use LV queues, LV semaphores or you have to write a reentrant VI that keeps calling Global Storage__P.vi in a loop until the pointer is released. The two first alternatives make your pointer system perform poorer than LV queues and the last alternative scales very badly with the number of simultanous data access to any pointer in the system. However you pointer system performs very very well in a situation when concurrent read-modify-write is not needed.

You must also remember that this system is totally asynchronous while queues MUST be synchronous to function properly.

LabVIEW probably uses C++ queue to control access to your Global Storage__P.vi. Only one thread at a time can access it, as it is not reentrant. And you naturally cannot make it reentrant.

I see it like this: It's an ordinary LV2 global with an array, and will perform just like any other LV2 global with arrays. About concurrency and stacks, I really don't know how to test this, can it be tested?

Open VI reference to N instances of a same VI that tries to use your pointers to perform something. Then increase N and see how it scales.

[bsvingen]

OK. Yes, i see that create can be speeded up. As the test is running now, its not far from worst possible case in "create". The test does 10000 iterations, and when half is done, the bool array searches linearly 5000 to 10000 indexes 5000 times before it hits, still this is faster than creating new queues.

When user calls the Get Data operation, he gets the content of the stack but the data stays also in the stack. If the user wants to modify the data in the stack, he/she needs to get the data using Get Data, then modify it outside your VIs, and then write it back

Yes, I agree. But why do you want to do that? and why do you want to do it simultaneously several places for the same element? This is afterall only a pointer system, a functional global with a reference. I use it for passing data.