Using Assembly for Arrays

[CAP2007]

I am new to this forum. Please understand I have no assembly knowledge at all but am interested if the following can be done using assembly.

ie If I have the following array:

A(1)=3
A(2)=5
A(3)=7
A(4)=9
A(5)=11
A(6)=13
A(7)=15
A(8)=17
A(9)=19
A(10)=21
A(11)=23
A(12)=25
A(13)=27

Now what I would like to do is eliminate all arrays whose value is evenly divisible by 5 for example:

Therefore ideally I would like to be able to do the following by removing blocks of the array, if possible, and building a new array.

B(1)=3
B(2)=7
B(3)=9
B(4)=11
B(5)=13
B(6)=17
B(7)=19
B(8)=21
B(9)=23
B(10)=27

I am wondering if I could build the above array like this:
Send A(1) to B(1)
Send chunk A(3) - A(6) to B(2) - B(5)
Send chunk A(8) - A(11) to B(6) - B(9)
Send A(13) to B(10)

What might be able to be done is store the start and end indexes so that I can send the chunk to the new array by concatenating it to the new array list. I have no idea if I made myself clear but thats the best I can do. If this helps the array can be 10's of millions of elements ranging with numbers 1 to n but all values will always be in ascending order and each will be a unique value. I hope I have desribed the issue clearly. Like I said before pardon my ignorance but I have no assembly experience and appreciate any help you gurus can provide me with.

Thanks,

Les

 

[Salem]

It's certainly one way of doing it, though I don't think it's particularly efficient.
Unless there are some properties of your data which you haven't mentioned yet, you have to examine each element in order to work out the length of a chunk, then you examine it again later in order to move the chunk to the new array.

Compare with this 'C' example which combines both steps into a simple access, compare, store sequence.

#include <stdio.h>
#include <stdlib.h>

size_t stripMod5 ( int *dst, const int *src, size_t len )
{
    size_t newlen = 0;
    while ( len )
    {
        int temp = *src++;
        if ( temp % 5 != 0 )
        {
            *dst++ = temp;
            newlen++;
        }
        len--;
    }
    return newlen;
}


int main ( ) {
    int a[] = {
        3, 5, 7, 9, 11,
        13, 15, 17, 19, 21,
        23, 25, 27
    };
    int b[100];
    size_t newlen = stripMod5( b, a, 13 );
    size_t i;
    for ( i = 0 ; i < newlen ; i++ ) {
        printf("%d\n", b[i] );
    }
    return 0;
}

So instead of counting the length of a chunk, then going off somewhere else to copy the chunk, it is just copied inline.


--
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.

 

[CAP2007]

Hi Salem,

Well I thank you very much for the code but I am not sure if it will do what I want it to do. Unfortunately I can not discuss exactly what I am working on since it is proprietary at the moment. I think that my idea will allow me to keep track of the chunks inline as I go through the filtering process. See Salem I need to go through the filtering process a number of times before I arrive at what I am trying to do and each time I go through the process it depends on the new updated array list. Perhaps Salem you can ask me for additional information that may help establish more clarity on trying t find a solution.

I thank you so much and look forward to your response,

Les

 

[Salem]

What language is the rest of the system written in?

I've got this feeling that you've chosen "asm" as some last resort optimisation in an attempt to boost the performance of the system. In other words, you've already written something, and it just isn't fast enough.

How many filter stages are there? You talk about removing all multiples of 5, do you then have another pass to remove say all multiples of 7?

But before we go there, we need to make sure that the algorithm you've chosen is the best there is. The analogy is comparing a QuickSort written in a high level language with a BubbleSort written in ASM. The QuickSort will win given a large enough data set.

To answer your first question, the answer is "yes", you can implement this in assembler.

You also need to say which processor you're using. Assembler is not portable at all, so you need to be very specific about the target system this will run on.


--
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.

 

[CAP2007]

Hi Salem,

Once again thank you for your reply. Actually the only reason I was considering assembly was to resolve a scheme I thought of about moving chunks within an array to another array and I thought this would be doable in assembly vs Visual Basic which is waht I write in. As far as to how large a set of numbers we are talking about it could be as large as 1,000,000,000 long integers and they all will be unique. BTW I dont know if this helps but the current scheme assures all numbers will be in ascending order. I am going to spend some time thinking about my approach. Whats tantalizing is that on paper this method looks great but it sseems so tricky to put it into viable code <S>, you know that feeling I am sure.

I will keep you posted as I move forward.

Thanks again,

Les

 

[Salem]

For what it's worth, I would consider an approach which applies all the filters at the same time, and then only move the integer to another array if it passes all the tests.

This would save all the test-and-move, test-and-move iterations which would really soak up the time. So it would be test-test-move instead.

> it could be as large as 1,000,000,000 long integers
Which would need 4GB of memory to store them.
The maximum user address space on a 32-bit windows machine (for example) is 3GB IIRC.
And that's before you allocate another array to store the result in, and all your user code. Further, if your machine has less than the full address space populated with real memory, you're going to be swapping a hell of a lot.

Also, I would suggest you consider C or C++ in the first instance. I don't know how poor VB is in this respect, but my impression is is that if the increase from VB to ASM is 100%, then the increase from VB to C/C++ will be 95%. In other words, the last few % will take a disproportionate amount of effort to gain.

Writing a DLL in C say would be fairly trivial to call from VB (as far as I know).


--
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.