Benchmarking Block Swapping Algorithms

This is a re-print of my Dr. Dobb’s article from April of 2012. The original article used to be available: https://www.drdobbs.com/parallel/benchmarking-block-swapping-algorithms/232900395 It is still available https://web.archive.org/web/20130130063936/http://www.drdobbs.com/parallel/benchmarking-block-swapping-algorithms/232900395 Below is the recreated version, with code fixes to one of the algorithms. Swapping two elements within an array quickly is simple, requiring a single temporary storage element. Swapping […]

Two Simple Sorting Algorithms

Merge Sort was invented by John von Neumann in 1945. Many implementations have been shown in books and on the internet. However, in-place implementations have been difficult to accomplish, due to the need for an in-place merge, which only recently became available in standard C++, and is not available in other languages. In this blog, […]

Parallel In-Place Merge

This is a re-post of my 2012 article in Dr. Dobb’s Journal, that is still available through the amazing WayBackMachine web archive. In my article on parallel merge, I developed and optimized a generic parallel merge algorithm. It utilized multiple CPU cores and scaled well in performance. The algorithm was stable, leading directly to Parallel Merge Sort. […]

Average Fun

Computing an average or two numbers seems simple and innocent enough of an operation. Here is an example from a C++ computer science text book: int m = (a+b) / 2 where a and b are also int’s, which are signed 32-bit values on most computers. This code seems innocent enough: add two integers, divide […]

Sorting 19X Faster Than C++ Parallel Sort

(Rewritten on October 28, 2023) In my previous blog https://duvanenko.tech.blog/2020/02/03/faster-c-sorting/ Standard C++ Sort algorithm was benchmarked running on a single core at 11 million 32-bit integers per second. Its parallel version scaled up to 93 million integers per second on a 48-core Xeon processor AWS node (C5.24xlarge) – 8X speedup. Also, my implementation of Parallel […]

Feeling In-Place with Functional

Functional programming paradigm has infiltrated every modern programming language. Functional is considered a safer coding method, and lends itself to parallelism as well. A typical function in function programming style takes an input and returns an output. Input can be a single item or an array. Output can be either as well. This enables cascading […]

Computer Architecture is Non-Functional

Functional programming has been around since the late 1950’s, based on lambda calculus concepts dating back 100 years. It has been embraced by just about every modern language, because of guarantees it offers. Immutability is one property of functional programming, where functions never change a variable, but instead return a new one. When an function […]

Even Faster Sorting in C#

My earlier Faster Sorting in C# blog described a Parallel Merge Sort algorithm, which scaled well from 4-cores to 26-cores, running from 4X faster to 20X faster respectively than the standard C# Linq.AsParallel().OrderBy. In this blog, I’ll describe an even faster Parallel Merge Sort implementation – by another 2X. Performance of the New Approach C# […]

To In-Place or To Not-In-Place

What Is It? Computing constantly provides space-time trade-offs. To make an algorithm faster, more space can be used. Or, if space is at a premium, then a slower and more space efficient algorithm can be used. This kind of a trade-off occurs in every aspect of computing, such as software development and chip design. In […]

Parallelism: Perform No Worse

The number of cores in modern processor is growing. For quite a while we were stuck at 2 or 4 cores. But, lately the number of cores have grown to 6 and 8 even for consumer processors, and to 14 cores for Intel Xeon workstation and cloud CPUs, and 32 cores for AMD desktop and […]

Algorithm Performance

Measure, Question, Improve, Do It Again…