Programming Exercise: Sorting Algorithm w/Dynamic AOI – Results

Paullys50

Lifetime Supporting Member
Join Date
Jan 2006
Location
WI
Posts
2,188
First a disclaimer, this is purely an exercise which I found to be interesting and decided to share my results.

A while back there was a post on changing the array size within and AOI dynamically. I was curious about this and set out to explore some possibilities for its use. At the time I had watched a documentary about sorting algorithms and realized that a sorting AOI which could automatically adjust to the size of the dataset input into it could prove useful on the production floor (think motor runtime, valve/actuator activation counts as it relates to life cycle and PMs). I thought it would be a fun exercise to see if I could create a self-aware solution which minimized impact on logic execution.

The solution results: 5,000 random values ranging from -2,147,483,648 to +2,147,483,647 are sorted in descending order in ~ 400ms using a 1756-L73 controller. This also includes 5000 indexes, 1 index per value so I can track the identity of each value during the sort.

Actual results of PLC sorting:
NoF1qzy.png



Further tests produced:
1,000 random values ~ 50ms
100 random values ~ 3ms
50,000 random values ~ 5,845ms
375,000 random values ~ 66,027ms

As a baseline, using the SRT instruction it sorts 5,000 random values in ascending order w/no index reference took ~ 1100ms. If I remove the index consideration of the sorting AOI, the AOI can sort 5000 random values in ~ 270ms!

Testing Information:
I used Excel and vba to generate the random values, some more VBA allowed me to download the random values to the PLC, trigger the sort, then upload the values back into Excel for a nice chart to confirm the sort was successful. To confirm impact on scan times I simply looked directly at the monitor tab of the task the logic was in and referenced the “max” scan time. I reset this prior to each test and the AOI was triggered on a one-shot. The logic in a “steady’ state was running at 0.10 ms, so negligible.

Algorithm:
When first playing with the sort concept I used a “bubble” sort. This worked but as I progressed I found that a “shell” sort had little bit better performance-wise and less logic. I did not track the data to show this. I did not attempt any other type of sorting algorithm as I was happy with the results. I have decided not to post my source code as to encourage others to try to create their own. Hint - find a pascal example of the algorithm you wish to try and start there, pascal is extremely close to structured text and requires minimal changes to port. It would be interesting to compare the results of other sorting algorithms if people wish to try.

Here is a screen shot of the AOI and parameters into it. Notice they have an array size of [1].

tgqYrPz.png
vTNmDmE.png


Process:
Since I want to maintain an index with its associated value, the data is really best described as a 2 dimensional array: Data[index,value]. While I was able to use a 2 dimensional array and create the shell sort solution, there was large impact on scan time, and I could not make the AOI array sizes dynamic as this only works on one dimensional arrays. Hence my final AOI parameters are one-dimensional for a total of 4. 2 for the unsorted data index and value and 2 for the sorted data index and value. These 4 tags are required to be the same type and length. The AOI adjusts accordingly.

Conclusions:
The dynamic ability in the AOI is very convenient for this example. I simply had to resize the 4 array tags input into my AOI (or reference other tags of varying array sizes), the AOI definition did not have to change. I spent more time adjusting my VBA so I could write/read the test values (went from simple "fixed" code to "I should make this dynamic to match..."). It was very easy to change from 10 – 100 – 1000 – 5000 – 50,000 - 375,000 and test the logic. Examination of the implementation and results it produces are positive IMHO. It works with minimal impact on scan time unless you are trying to sort a large dataset which is highly unlikely in a PLC. Considering that a sort function probably does not to be ran per scan calling it from an event, or dropping into a 1 sec periodic tasks seems very reasonable if you wish to process up to 50,000 values or so. Single AOI that doesn't require changes to adapt to varying data sizes, I'll take it!




s!AiDHoUqNwjoPg4VIMIvrBfB4OWBslA
ncb9t
ncb9t
 
Last edited:
This shows why Rockwell software is better than most. I don't know of any other PLC that can handle dynamic memory allocation. I,my customers, often need to use dynamic memory allocation for Ethernet buffers. If the PLC doesn't have the ability to dynamically size the buffer life becomes harder.

Shell sort is a good choice.
It isn't made clear how many iterations are done per scan. Obviously sorting a large array in one scan is not possible.
 
It isn't made clear how many iterations are done per scan. Obviously sorting a large array in one scan is not possible.

I didn't track how many loop iterations it took to sort all the random values, however I can assure you it as was all done in 1 scan. The scan times reflect this.

1,000 random values ~ 50ms
100 random values ~ 3ms
50,000 random values ~ 5,845ms
375,000 random values ~ 66,027ms


Edit: You do have to increase the watchdog timer to ensure you don't fault the controller.
 
Last edited:
This shows why Rockwell software is better than most. I don't know of any other PLC that can handle dynamic memory allocation. I,my customers, often need to use dynamic memory allocation for Ethernet buffers. If the PLC doesn't have the ability to dynamically size the buffer life becomes harder.

Shell sort is a good choice.
It isn't made clear how many iterations are done per scan. Obviously sorting a large array in one scan is not possible.

There isn't any "dynamic memory allocation" occurring here Peter.

The array is being passed to the AOI as an "In/Out" parameter, which means it is "by Ref". The AOI is working directly with the actual data.

I'd like to see the code of the sorting, I'm assuming it is inspecting the SIZE of the array to determine processing limits.

I can see uses for the sampled 100 or 1000 iterations, being completed in 3 and 50 mS respectively, but would be very concerned on the scan time hit for anything above that. 6 seconds to sort 50,000 values means that the controller is doing nothing else.

Perhaps this is a case for putting the sorting logic in the continuous task, and putting application logic into periodic tasks, which by definition gives the sorting a lower priority.

But that 6 second sort time for 50,000 values will go out the window, being constantly interrupted by the "mundane" task of controlling the process.

In conclusion, if you've got any serious sorting to do, do it with a "parallel processor" - several methods could be employed, including...

1. another processor
2. SQL
3. VBA
4. enter your own choice here
 
But that 6 second sort time for 50,000 values will go out the window, being constantly interrupted by the "mundane" task of controlling the process.

Once I get my hands on an L8x processor I'll run the same tests, would be a good metric to see how much faster the L8 series over the L7. Rockwell says 5 - 20x the performance, if it can hit 10x with this example, that's something to be impressed by, closer to 20x and that's a pretty big wow.
 
There isn't any "dynamic memory allocation" occurring here Peter.
I know but it is still better than most other PLCs where if I write PLC code to emulate an AB MSG block the buffer size is fixed. Most of my customers CAN NOT write code for Ethernet communications if the PLC only supports socket communications. I end up writing the code that I share so people can talk to our controllers but different customers have different needs as far as how much data they need to pass so the buffer size always seems to change.


I can see uses for the sampled 100 or 1000 iterations, being completed in 3 and 50 mS respectively, but would be very concerned on the scan time hit for anything above that. 6 seconds to sort 50,000 values means that the controller is doing nothing else.
Yes, that is why I was hinting at only doing a fixed number of iterations per scan to keep the processing time per scan down and use a done bit so one knows when the sorting is done.

Most of the time any sorting doesn't need to be done in one scan anyway.

Another issue is the sort method. Shell sort is good for batch sorting in place. Insertion sort is better if sorting new items one at a time as they arrive. It should be possible to find the proper place for new items in one scan if the COP command doesn't take too long when inserting a new item at the beginning of a list.

I agree that controllers shouldn't be use for sorting more than a few items.

There are websites that compare sort methods. Sort in place methods that don't use a stack or heap are the best.
 
Further tests produced:
1,000 random values ~ 50ms
100 random values ~ 3ms
50,000 random values ~ 5,845ms
375,000 random values ~ 66,027ms
@Paully's5.0: did you compare the efficiency of your AOI's code against the same code running in a conventional routine with fixed-length arrays?
 
@Paully's5.0: did you compare the efficiency of your AOI's code against the same code running in a conventional routine with fixed-length arrays?

Not directly, however everything was developed in a conventional routine and tested before I created the AOI. The only time there was a significant difference in scan time was when i used 2 dimensional arrays or changed the number of values to sort.

Keep in my what daba is getting at, I'm not actually changing any array sizes in the logic at runtime. The AOI is flexible, meaning that it can determine the size of any fixed-length array passed into it and adapt accordingly. Since the parameters are InOut and passed by reference, the AOI is directly accessing the tags I passed to it.
 
Keep in my what daba is getting at, I'm not actually changing any array sizes in the logic at runtime.
I understand the point. My question is more related to know what's more efficient (speaking about time). Let's take 50,000 random values: your code (inside teh AOI) can proccess those values in 5,845ms. How long does the same code require to sort the same group of values when you put it in a plain routine?
 

Similar Topics

Hello colleagues, Some time ago I started my adventure with programming. With your help and the courses, things are starting to come together...
Replies
13
Views
580
Dear All, I need a sample PLC program to count the output pulse of a mass flow meter so that a specific amount of mass (for example 100gm)can be...
Replies
2
Views
77
Hi Please I have zeilo smart relay #SR2A201BD but I don't have it's programming cable. Can I use any general usb/rs232 converter? Or need...
Replies
2
Views
78
Hi, Does anyone have thoughts or know of, can point in the right direction any published materials with a plumbing centric point of you explaining...
Replies
1
Views
125
In this sample programming, what does U4 mean? Any assistance would be greatly appreciated.
Replies
8
Views
169
Back
Top Bottom