Testing (and Timing) String Reversal Functions
Tags: javascript, programming, csharp
Published: 2019-07-20 14:07:54

---
title: Testing (and Timing) String Reversal Functions
published: true
description: Testing the speed (or lack thereof) of code
tags: javascript, programming, csharp
series: reversing a string
---
So [Sarah Chima](https://dev.to/sarah_chima/reverse-a-string-four-javascript-solutions-2nbm) wrote an article about reversing a string, done four different ways. A few folk wrote in with other solutions. I wrote in with some too.

Then it was suggested that we try to work out which really is the fastest. What follows is me trying.

So I need first of all to mention my working environment. It's call [Lychen](https://github.com/axtens/Lychen) and it's a wrapping of the V8 JavaScript engine in a C# command line application with access to some C# objects, methods and properties. Lychen is &laquo;not supposed to be cutting-edge. Rather, it's on the spine of the blade, about as far from the cutting-edge as one can get without leaving the blade altogether.&raquo; (see the [Wiki](https://github.com/axtens/Lychen/wiki)).

You might say to me, "Hey, what about [node](https://nodejs.org/en/)?" My response is usually along the lines of "I just can't get my head around the promises and the asynchrony. Maybe one day."

So here's the code.

```
const Console = CS.System.Console;
```
`CS.` exposes a large number of C# core and third party objects into the Lychen (V8) environment. Rather than keep typing `CS.System.Console` we create an abbreviation.
```
if (CSSettings.ContainsKey("/D")) {
  debugger;
}
```
On launch, `CSSettings` (a `Dictionary<string,object>`) receives all the command line parameters. In this case, if it's `/D` we debug.
```
const times = CSSettings.ContainsKey("/TIMES") ? parseInt(CSSettings("/TIMES"), 10) : 1000;
```
Similarly, here we check for the presence of `/TIMES` and if it's, say, `/TIMES:123` then `times` is set to `123`. Otherwise `times` defaults to `1000`. `/TIMES` exists because we want to be able to run each test many times. 

The first test of any routine usually takes a bit longer than subsequent runs due to operating system caching. We'll take many measurements and then average them in the hope of getting a better idea of how long things _really_ take. 
```
var original;
if (CSSettings.ContainsKey("/RANDOM")) {
  original = Array(12500)
    .fill(0)
    .map(function () {
      return String.fromCharCode(Math.floor(Math.random() * 256));
    }).join("");
} else {
  original = Array(500).join("lewd did i live - evil i did dwel").substr(0, 12500);
}
```
If the command-line contains `/RANDOM` we generate a test string of 12500 random ASCII characters. Otherwise we fill an array with some text and then truncate it to 12500 characters. 12500 was chosen because larger numbers caused the recursive functions to fail impolitely.
```
var reversed = Sarah_ForOf(original);
```
We use one of the following reversal functions to reverse the `original` test string so that we can double check that the reversal actually WAA (Works As Advertised).
```
function TimeTest(name, fn, original) {
  var Stopwatch = new CS.System.Diagnostics.Stopwatch();
  Stopwatch.Start();
  var answer = fn(original);
  Stopwatch.Stop();
  var ts = Stopwatch.Elapsed;
  return {
    name: name,
    ticks: ts.Ticks,
    reversed: answer
  };
}
```
We use C#'s `System.Diagnostics.Stopwatch` to track the run time of the function being tested. The parameters are: the name of the function, the function's reference, and the string to be tested. The `Ticks` of the `Elapsed` result of the run are returned along with the name and the results of the reversal. More about `Ticks` at the end.
```
function EmptyFunction(string) {
  return string;
}
```
We want to account for the cost of actually making the call, so we will time how long it takes just to load run an empty function that returns a string.

Next come the contributed routines.
```
const Sarah_SplitReverseJoin = (string) => string.split("").reverse().join('');

const Nathanael_SplitReverseJoin = (string) => [...string].reverse().join('');

function Sarah_ForOf(string) {
  let reverseString = "";
  for (let character of string) {
    reverseString = character + reverseString;
  }
  return reverseString;
}

const Sarah_Reduce = (string) => string.split('').reduce((rev, char) => char + rev, '')

function Sarah_Recursive(string) {
  return string ? Sarah_Recursive(string.substring(1)) + string[0] : string;
}

function Theophanis_SplitFor(string) {
  let result = string.split('');
  for (let i = 0, j = string.length - 1; i < j; i++, j--) {
    result[i] = string[j];
    result[j] = string[i];
  }
  return result.join('');
}

function Theophanis_SplitFor_Bruced(string) {
  let result = string.split('');
  for (let i = 0, j = string.length - 1; i < j; i++, j--) {
    const string_i = string[i];
    const string_j = string[j];
    if (result[i] !== string_j) {
      result[i] = string_j;
    }
    if (result[j] !== string_i) {
      result[j] = string_i;
    }
  }

  return result.join('');
}
```
I thought that checking for the need to swap before actually swapping would be a good optimisation. I was wrong, especially with respect to random data
```
function Bruce_ArrayApplyMap(string) {
  return Array.apply(null, new Array(string.length).fill(0).map(function (_, i) {
      return string.charAt(string.length - 1 - i);
    })).join("");
}

function Bruce_MapSortMap(string) {
  return Array(string.length)
  .fill({})
  .map(function (item, index) {
    return {
      index: index,
      character: string.charAt(index)
    };
  }).sort(function (a, b) {
    return a.index > b.index ? -1 : (a.index === b.index ? 0 : 1);
  }).map(function (item) {
    return item.character;
  }).join("");
}

function Bruce_Recursive1(string) {
  return (string.length === 1)
   ? string
   : Bruce_Recursive1(string.substr(1)) + string.substr(0, 1);
}

function Bruce_Recursive2(string) {
  if (1 >= string.length)
    return string;
  return (
    string.substr(-1) +
    Bruce_Recursive2(string.substr(1, string.length - 2)) +
    string.substr(0, 1));
}

function Bruce_CharAt(string) {
  const result = Array(string.length);
  for (let i = string.length - 1, j = 0; i >= 0; i--, j++) {
    result[j] = string.charAt(i);
  }
  return result.join("");
}

function Bruce_CharAt2(string) {
    const result = Array(string.length).fill(1);
    result.map(function (item,index) {
        let rhs = string.length - 1 - index;
        result[index] = string.charAt(index);
    });
    return result.join("");
}
```
All the functions in Sarah's posting along with those of other contributors.
```
const namesAndCodes = [{
    name: "Sarah_SplitReverseJoin",
    code: Sarah_SplitReverseJoin
  }, {
    name: "Sarah_ForOf",
    code: Sarah_ForOf
  }, {
    name: "Sarah_Reduce",
    code: Sarah_Reduce
  }, {
    name: "Sarah_Recursive",
    code: Sarah_Recursive
  }, {
    name: "Theophanis_SplitFor",
    code: Theophanis_SplitFor
  }, {
    name: "Theophanis_SplitFor_Bruced",
    code: Theophanis_SplitFor_Bruced
  }, {
    name: "Nathanael_SplitReverseJoin",
    code: Nathanael_SplitReverseJoin
  }, {
    name: "Bruce_ArrayApplyMap",
    code: Bruce_ArrayApplyMap
  }, {
    name: "Bruce_MapSortMap",
    code: Bruce_MapSortMap
  }, {
    name: "Bruce_Recursive1",
    code: Bruce_Recursive1
  }, {
    name: "Bruce_Recursive2",
    code: Bruce_Recursive2
  }, {
    name: "Bruce_CharAt",
    code: Bruce_CharAt
  }, {
    name: "Bruce_CharAt2",
    code: Bruce_CharAt2
  }
];
```
The names and functions to be tested.
```
var gathering = {};

for (let i = 0; i < times; i++) {
  namesAndCodes.forEach(function (item) {
    const eps = TimeTest("EmptyFunction", EmptyFunction, original).ticks;
    const result = TimeTest(item.name, item.code, original);
    if (!gathering[result.name]) {
      gathering[result.name] = [];
    }
    gathering[result.name].push(result.ticks - eps);
  });
}
```
Here we do the testing, looping from zero to whatever value `times` holds. We `forEach` through the `namesAndCodes` structure. We calculate the time it takes to run an empty function and then we subtract that from the ticks of the result of the test. `gathering` holds the result of each test in an array keyed to the name of the function.
```
const average = arr => arr.reduce((p, c) => p + c, 0) / arr.length;

Object.keys(gathering).map(function (item) {
  return [item, average(gathering[item])];
}).sort(function (a, b) {
  return a[1] > b[1] ? 1 : a[1] === b[1] ? 0 : -1;
}).forEach(function (item) {
  Console.WriteLine("{0,-28}{1} ticks", item[0], item[1]);
});
""
``` 
Report on the results: Convert the gathering object into array[,] of name and averge, sort on the second item so that fastest comes first, write the results to the console with the name left-justified in a 28 character field, followed by the ticks.

And the results?
```
>timer.ly  /TIMES:1000
Sarah_ForOf                 2141.86 ticks
Sarah_SplitReverseJoin      2444.758 ticks
Sarah_Reduce                2805.243 ticks
Bruce_CharAt                2842.139 ticks
Nathanael_SplitReverseJoin  3035.17 ticks
Theophanis_SplitFor         3142.142 ticks
Bruce_Recursive1            3319.84 ticks
Bruce_Recursive2            3451.674 ticks
Theophanis_SplitFor_Bruced  3616.858 ticks
Sarah_Recursive             4645.366 ticks
Bruce_ArrayApplyMap         5637.1 ticks
Bruce_MapSortMap            9754.566 ticks
Bruce_CharAt2               13721.967 ticks


>timer.ly  /TIMES:1000 /RANDOM
Sarah_ForOf                 1850.582 ticks
Sarah_SplitReverseJoin      2655.574 ticks
Theophanis_SplitFor         2815.478 ticks
Nathanael_SplitReverseJoin  2832.566 ticks
Bruce_CharAt                2842.439 ticks
Sarah_Reduce                2845.746 ticks
Bruce_Recursive2            3224.578 ticks
Bruce_Recursive1            3306.136 ticks
Theophanis_SplitFor_Bruced  3428.827 ticks
Sarah_Recursive             4258.6 ticks
Bruce_ArrayApplyMap         5421.202 ticks
Bruce_MapSortMap            9748.012 ticks
Bruce_CharAt2               13477.231 ticks
```
On my computer there are 10,000,000 ticks per second (using CS.System.Diagnostics.Stopwatch.Frequency). According do the [documentation](https://docs.microsoft.com/en-us/dotnet/api/system.diagnostics.stopwatch.elapsedticks?view=netframework-4.8) "Each tick in the ElapsedTicks value represents the time interval equal to 1 second divided by the Frequency."

The bottom line? Sarah's ForOf and SplitReverseJoin are by far the fastest. Theophanis's SplitFor is also really good. That said, the differences are in microseconds or less. 

*NOTE*: All suggestions on how to improve this testing regime gratefully received. Thanks in advance.