Performance impact of sorted arrays.

Computer performance is filled with unexpected results. This morning on  stack overflow I found  such a result, and decided to replicate it in C#.

Take an array of random integers and sum only the big integers.  Next, sort the array and re-sum the big integers. Does sorting the array affect the time taken to compute the aggregation? Let's code it up:
The results:

Wow, it's 5 times faster to perform this sum over a sorted array then an unsorted array. What's going on? Branch prediction!  If you've never heard of branch prediction check out the stack overflow answer that inspired this post.

You can quickly replicate this experiment using LinqPad and MeasureIt.Net, by loading this file.

Comments

Post a Comment

Popular posts from this blog

Finding CLR exceptions without visual studio

(If you want to understand what exception code 0xe0434352 is, read this post ) Often exceptions are thrown and caught and you don't see them. You probably know how to debug this in Visual Studio, so let me show you how to do it in cdb. Sample Code: class Program { static void Main(string[] args) { foreach (var x in Enumerable.Range(0,2000)) { Thread.Sleep(TimeSpan.FromSeconds(1)); Console.WriteLine("Hello World"); ThrowAndCatchException(); } } private static void ThrowAndCatchException() { try { throw new NotImplementedException(); } catch(Exception) { } } } Output of the application: Hello World Hello World Hello World Nothing about an exception, but you're sure it's happening behind the covers -- fire up cdb: C:\Program Files\Debugging Tools for Windows (x64)>cdb -pn consoleapplication3.exe <SNIP> ModLoad: 000007fe`f7e90000 000007fe`f7eb4000 C:\Windows\Mi
Read more

Why do I keep getting exception code e0434352?

If you want to know how to debug CLR exceptions using cdb then read this post . Exception code e0434352 is the exception code used internally by the CLR to represent most exceptions(*). Regardless of if you throw a System.NullReferenceException or a System.ArgumentException in C#, you'll throw a SEH exception e0434352 under the covers. A fun way to validate this theory is to watch what happens to the CLR exceptions settings in cdb. Fire up cdb, and see the state of clr exceptions: 0:000> .shell -ci "sx" findstr clr clr - CLR exception - second-chance break - not handled clrn - CLR notification exception - break - handled .shell: Process exited Now, set the exception handler for exception number e0434352 and recheck the value of the clr exception handler: 0:000> sxe e0434352 0:000> .shell -ci "sx" findstr clr clr - CLR exception - break - not handled clrn - CLR notification exception - break - handled .shell: Process exited Armed with
Read more

Powershell script to enable windows to capture localhost traffic in wireshark

If you want to understand why the following scripts work read this post . Otherwise just paste the following into an elevated powershell window: Setup windows networking to allow localhost capturing in wireshark: # Find the network configuration that has the default gateway. $defaultAdapter = Get-WMIObject Win32_NetworkAdapterConfiguration | ? {$_.DefaultIPGateway} if (@($defaultAdapter).Length -ne 1) {throw "You don't have 1 default gateway, your network configuration is not supported" } # Route local IP address via the default gateway route add $defaultAdapter.IPAddress[0] $defaultAdapter.DefaultIPGateway Write-Host "Start capturing on localhost by connecting to $($defaultAdapter.IPAddress[0])" Return windows networking to normal configuration: # Find the network configuration that has the default gateway. $defaultAdapter = Get-WMIObject Win32_NetworkAdapterConfiguration | ? {$_.DefaultIPGateway} if (@($defaultAdapter).Length -ne 1) {throw "Y
Read more