[2005] Fastest way to change array

[Ivenesco]

How is the fastest way to change some bytes in array? I have this code:

For i As Integer = 0 To x
      input(i) = input(i) Xor key(intKey)
Next

But I'm looking for something faster. I tried to use direct access to memory via marshal, but it's much slower... Does anybody know faster way?

[dbasnett]

quantify slow and fast?

[dbasnett]

        Dim bigA(100000) As Integer, keyA(100000) As Integer
        Dim stopW As New Stopwatch, someRandom As New Random
        stopW.Reset() : stopW.Start()
        For x As Integer = 0 To bigA.Length - 1
            keyA(x) = someRandom.Next(1, Integer.MaxValue)
            bigA(x) = bigA(x) Xor keyA(x)
        Next
        stopW.Stop()
        Debug.WriteLine(stopW.ElapsedTicks.ToString)
        Debug.WriteLine(stopW.ElapsedMilliseconds.ToString)
        Stop

9 ms., in the debugger, on my 1.8Ghz laptop. <---Quantified

[Ivenesco]

I don't know what is your code. You mean, that is fast enough? My question is: "what is faster?".
If you want to know whole function, look at "code it better" section.

[dbasnett]

How big is x? If it is 10, who cares. If it is Integer.MaxValue that is different.

For i As Integer = 0 To x
      input(i) = input(i) Xor key(intKey)
Next

My code was your code, sort of, but quantified.

You asked the question here, but somehow I was supposed to know to look somewhere else, and then go look for it. When all you had to do was put it here

Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()

        Dim intKey As Integer = 0
        Dim x As Integer = input.Length - 1
        Dim x2 As Integer = key.Length
        For i As Integer = 0 To x
            If intKey = x2 Then
                intKey = 0
            End If
            input(i) = input(i) Xor key(intKey)
            intKey += 1
        Next

    End Function

[dbasnett]

1 ms.

        Dim stopW As New Stopwatch, someRandom As New Random
        Dim input(100000) As Byte, key(50000) As Byte
        'make up some data
        For y As Integer = 0 To input.Length - 1
            input(y) = CByte(someRandom.Next(1, Byte.MaxValue + 1))
            key(y \ 2) = CByte(someRandom.Next(1, Byte.MaxValue + 1))
        Next
        'now I have data, what is the speed of your code
        'debugger, 1.8Ghz laptopm
        stopW.Reset() : stopW.Start()
        Dim intKey As Integer = 0
        Dim x As Integer = Input.Length - 1
        Dim x2 As Integer = key.Length
        For i As Integer = 0 To x
            If intKey = x2 Then intKey = 0
            input(i) = input(i) Xor key(intKey)
            intKey += 1
        Next
        stopW.Stop()
        Debug.WriteLine(stopW.ElapsedTicks.ToString)
        Debug.WriteLine(stopW.ElapsedMilliseconds.ToString)
        Stop

[Ivenesco]

No, I have only one question here: what can be faster than access like "array[x]=something". X isn't important here.
What mean 1ms? I want to know how I can do it faster. If you have 1ms with this code, so I need < 1ms

[dbasnett]

what is the old adage, 10% of the code does 90% of the work. is this just an academic deal?

1 ms. = 1 millisecond.

When I first tried this, and now I wish I had left it alone, I had the array size set to 10,000. Then the speed was 0 ms. So there is your answer, make your arrays 10,000 elements long and it will be faster.

[Ivenesco]

.......
I need faster processing, not smaller x... I'm writing algorithm as fast algorithm, as it's possible. Divide 100,000 by 1 ms, and you will get 100k/1ms. Now divide 10,000 by 0,1ms, and you will get... 100k/1ms. Speed is the same.
And no, it isn't deal. It's only my own test. I'm looking for best and fastest programming tricks.

[dbasnett]

.......
I need faster processing, not smaller x... I'm writing algorithm as fast algorithm, as it's possible. Divide 100,000 by 1 ms, and you will get 100k/1ms. Now divide 10,000 by 0,1ms, and you will get... 100k/1ms. Speed is the same.
And no, it isn't deal. It's only my own test. I'm looking for best and fastest programming tricks.

Lets stop talking about milliseconds. The other measure I showed was ticks. On my PC, for 100,000 calculations it took, on average, a little less than 7,000 ticks.(a tick is 100 nanoseconds, 1 nanosecond is about 14 inches long)
That means the average was 7 nanoseconds/loop. By running in release mode I got the number to 5 nanoseconds / loop.

Of the 7000 ticks, roughly 1300 of them were consumed by

        For i As Integer = 0 To x
        Next

I got involved in a calculation of Factorials. When I started the code it took around 60 seconds to calculate 10,000! When I was finished it took .3 seconds.

Reductio ad absurdum

[Ivenesco]

I don't understand you. I ask for faster way to change bytes in memory, and you give me tips to loop... There is many ways to reduce processing time, but I'm asking about arrays, and memory, not loops... In case of loops: if you use long, It'll take more time than for int (for the same number!). Maybe for byte (2 loops or more, one inside another) It'll take less? I'll try, but once again: my question isn't about it...

[dbasnett]

What do you want?
What trade-offs? Do you want a 1% speed reduction, 10%, 50%?
Would 10% speed reduction be OK if it took 10 times the amout of memory?

Do you have reason to think the code is not efficient?
Why do you think there is a significantly faster way? IMO significant would be 50%.

If this were part of a real application, and the application by your definition was slow, would you single out this piece of code, or would you find the real bottleneck?

[Shaggy Hiker]

I don't think you will find a faster way in .NET than what you are doing. You are XORing values, and there is no faster way to access a value in an array than indexing like that. However, since you are XORing values, there might be a faster way depending on what the data types are. If you are using bytes, then you could do a faster job by using integers, even with the wasted three bytes. If you are using integers, then to make the code faster you will have to move away from .NET.

The XOR instruction is part of the RISC subset of the Pentium class processor, and can execute at an exceedingly fast rate, but it won't in .NET. If you were able to write inline ASM for that, you might be able to get a 20x increase in speed, or possibly even more. Furthermore, on all modern processors from the MMX on up, it may be possible to xor a whole block of an array against another array, but that can only be done in ASM to the best of my knowledge (possibly in C/C++, as well, but possibly not).

As long as you are in .NET, you are going as fast as you can as long as you are working with integers.

[jmcilhinney]

If you want to speed things up then use unsafe code (i.e. pointers) in C#. VB was never built for speed so if speed is an issue then you should not be using VB in the first place. That said, one of the big pluses of the .NET platform is the fact that you can use different languages to create different parts of your app. You might create an application in VB for its simplicity but reference a library written in C# for the ability to use unsafe code to speed up computationally intensive operations. You might even reference a library written in C++.NET, a COM component written in C++ or use PInvoke to call functions exported from unmanaged C++ libraries. .NET is a toolbox and if Vb is the only tool you ever use you simply can't get the best results all the time.

[Ivenesco]

I don't think you will find a faster way in .NET than what you are doing. You are XORing values, and there is no faster way to access a value in an array than indexing like that. However, since you are XORing values, there might be a faster way depending on what the data types are. If you are using bytes, then you could do a faster job by using integers, even with the wasted three bytes. If you are using integers, then to make the code faster you will have to move away from .NET.

The XOR instruction is part of the RISC subset of the Pentium class processor, and can execute at an exceedingly fast rate, but it won't in .NET. If you were able to write inline ASM for that, you might be able to get a 20x increase in speed, or possibly even more. Furthermore, on all modern processors from the MMX on up, it may be possible to xor a whole block of an array against another array, but that can only be done in ASM to the best of my knowledge (possibly in C/C++, as well, but possibly not).

As long as you are in .NET, you are going as fast as you can as long as you are working with integers.

Thanks for this hint. This possibility with ASM sounds great
(Maybe C++ code and ASM block within? I heard It's possible.)

If you want to speed things up then use unsafe code (i.e. pointers) in C#. VB was never built for speed so if speed is an issue then you should not be using VB in the first place. That said, one of the big pluses of the .NET platform is the fact that you can use different languages to create different parts of your app. You might create an application in VB for its simplicity but reference a library written in C# for the ability to use unsafe code to speed up computationally intensive operations. You might even reference a library written in C++.NET, a COM component written in C++ or use PInvoke to call functions exported from unmanaged C++ libraries. .NET is a toolbox and if Vb is the only tool you ever use you simply can't get the best results all the time.

So it's possible to add Visual C++ iso/ansi function to .NET project? If yes, can you give me example? It'd be great way to add very fast algorithms to my .NET projects.

[jmcilhinney]

Any Windows API example on the forum can show you, or you could look up platform invoke on MSDN.

[Atheist]

I dont know any ASM, but I've thrown together a C++/CLI DLL that you can try..I've tested it against your function in the "Code it better" section and from what I can see it performs better.

Altough I suppose it would be even faster with something even more low level, like C++ without CLI, or as been mentioned, ASM.

[Ivenesco]

Can you show me sourcecode?

[Atheist]

The entire project was 11 mb in size (quite surprising, regarding the small amount of code), so I couldnt attach it to the post, but I could attach the one file that contained the "main" code. Though I cant do it for another 2-3 hours, as I'm not at that computer right now.

Altough in essence, it doesnt contain more than the exact function you posted in the Code it better section, but in C++.

Edit: I suppose I could rewrite the C++ function to show you how it looks. Hold on...
Edit 2: Ah no need to do that, I just realised you can just run the DLL in the .NET refractor and you'll see all the source code