# Palindromes and more

Jun 06, 2016

I decided to write this article from a question I saw in stackoverflow.com

Here the link to the question.

The questioner tries to write an algorithm to identify whether a “word” is a palindrome or it is not. The algorithm is written using the Java programming language

I do not want to analyze the algorithm proposed by the questioner, but I want to analyze the most voted answer algorithm. The latter has 73 votes versus 65 votes that have the accepted answer (to today’s date, June 6, 2016).

Here the link to the algorithm that I want to analyze.

Here the code:

The algorithm works correctly and the logic is very intuitive. Basically compares for *equality* the input word against its reverse.

The problem with this algorithm is that it is very inefficient compared to the optimal algorithm.

I made a comment to the author of the algorithm on Stackoverflow: “Compare the complexity of your algorithm with respect to others.”

The user @aioobe replied: “I think it’s the same complexity as the other solutions, no?”

He is right.

I was not very specific in my comment. @aioobe surely assumed that I was referring to the asymptotic computational complexity and he is ok, because usually, when we say “complexity” without specifying anything else, it is assumed that we are referring to the *asymptotic computational complexity*.

### Asymptotic Computational Complexity

*Asymptotic asymptotic computational* means how the algorithms respond in time and space as the input grows.

It is usually associated with the O-notation introduced by Paul Bachmann in his book Die Analytische Zahlentheorie in 1894. [1]

This way we can measure the scalability of algorithms without relying on machine architecture, CPU speed, the programming language in which is implemented the algorithm, etc…

While it is very useful in many circumstances, this method of measurement it is not accurate, but it is **approximated**.

For more information on O-notation and asymptotic complexity, see [2].

### Concrete Computational Complexity

Another way to measure algorithms is no use approximations but concrete quantity of operations, depending on the input to the algorithm.

For example, imagine the algorithm to find the minimum (or maximum) of \( n \) elements. We can say that the algorithm has *linear complexity* (in time), or the algorithm is \( O(n) \). But specifically, the algorithm needs comparisons to find the minimum element.

### Back to Palindromes

Again, the code of the algorithm.

I called *Algorithm I* to the previous code. (“I” as inefficient).

We could say that *Algorithm I* is \( O(n) \), but, how can we guarantee it without knowing the complexity of the components in which the algorithm is based?

To do this, we must review the Java documentation. For example, consider the String.equals() function. [3]

As you may have noticed on the previous page, the Java documentation does not include the time and space complexity of algorithms and data structures.

I consider this a failure, because it hinders us specifying the complexity of our algorithms, at least of the algorithms that are based on classes provided by Java.

To continue trying to specify the complexity of the *Algorithm I*, we have no choice, we have to review the source code of Java classes.

Consider the source code of String.equals() (click on the link and find the equals function.)

As you can verify the code String.equals() has linear complexity in time, \( O(n) \).

Specifically, String.equals() does \( n \) comparisons (*inequality*). (Beyond the noise imposed by Java, such as casts, instanceof, etc …).

The space complexity of String.equals() is constant, that is, \( O(1) \).

This means that it uses a constant memory beyond the input of the algorithm.

### Determining the complexity

We will determine the complexity of the *Algorithm I* analyzing each component.

String.equals(). Linear time, \( n \) *inequality comparisons*. Constant space.

StringBuilder.reverse(). Linear time, \( 2 \left\lfloor\dfrac{n}{2}\right\rfloor \) assignments. Constant space.

StringBuilder.toString(). Linear time, \( n \) assignments. Linear space, \( n \) elements.

StringBuilder constructor. Linear time, \( n + 16 \) assignments. Linear space, \( n + 16 \) elements.

So the overall complexity of *Algorithm I* is:

**Time**: In the worst case, when the word is a *palindrome*, this algorithm takes \( n \) *inequality* comparisons and \( 2n + 2 \left\lfloor\dfrac{n}{2}\right\rfloor + 16 \) assignments.

**Space**: \( 2n + 16 \) elements.

As you can see, this algorithm is very inefficient, it uses a lot of memory (unnecessarily) and as discussed below, takes over \( 8x \) operations optimal algorithm.

### Improving the algorithm (naïve version)

Call the following code *Algorithm N* (N as naïve). *Algorithm N* presents a substantial improvement over the *Algorithm I*.

**Time**: In the worst case, when the word is a *palindrome*, this algorithm takes \( n \) *inequality* comparisons.

**Space**: Constant

No extra memory usage and runs approximately \( \dfrac{1}{4} \) of operations that the *Algorithm I*.
While the code is a bit more complex now, it is an easily understandable code, the increased code complexity is negligible compared to the improvement in efficiency.

### Optimal Algorithm

As we can see in the picture below, there is no need to do \( n \) comparisons to determine whether a word is a *palindrome*.

It is enough to do just (about) half the comparisons:

- If n is even, it performs \( \dfrac{n}{2} \) comparisons
- If n is odd, it performs \( \dfrac{n - 1}{2} \) comparisons.

The following code will be called *Algorithm O* (O as optimal).

**Time**: In the worst case, when the word is a *palindrome*, this algorithm performs \( \left\lfloor\dfrac{n}{2}\right\rfloor \) *inequality* comparisons.

**Space**: Constant

*Algorithm I*, detailed analysis

As explained earlier, the *Algorithm I* is much more inefficient than *Algorithms N* and *Algorithms O*.

But besides the complexity analysis, we have to consider other issues that affect the efficiency of the *Algorithm I*.

Each component used in the *Algorithm I* come with certain performance penalties that go unnoticed.

Let us analyze in detail.

#### Construction of StringBuilder

- Dynamic memory allocation of the StringBuilder object (heap, free store, or whatever you call it).
- Zero-Initialization of members of StringBuilder. [4]
- Dynamic memory allocation of the StringBuilder’s internal array.

According to the documentation, the size of the internal array is equal to 16 characters plus the size of the original String. [5] - Zero-Initialization of Array’s members. Length and the array itself. [4]
- Copy of the bytes of the original String to the StringBuilder’s internal array.

#### reverse() (StringBuilder)

- Mentioned above. This function does not use additional memory and it is efficient at runtime.

#### toString() (StringBuilder)

- Dynamic memory allocation of the String object (heap, free store, or whatever you call it).
- Zero-Initialization of members of String. [4]
- Dynamic memory allocation of the String’s internal array.
- Zero-Initialization of Array’s members. Length and the array itself. [4]
- Copy of the bytes from the StringBuilder’s internal array to the String’s internal array.

#### equals() (String)

- Mentioned above. This function does not use additional memory and it is efficient at runtime.

#### Garbage Collection

- The GC must release any additional memory (unnecessary) that was used and obviously this operation is not “free.”

#### Data Cache Misses

- Another drawback associated with unnecessary memory consumption is the probability that our objects are too large to fit into the cache, causing cache misses impacting on runtime performance.
- Another factor that increases the probability of
*cache misses*are the indirections (references, pointers) to distant memory locations.

### Memory footprint

To analyze the memory consumption of *Algorithm I*, we will use a concrete example. We will use a 9-char *palindrome*, the word is “evitative”.

While memory consumption of *Algorithm I* depends on the Virtual Machine and the Runtime Environment that we are using, in this case we will use a specific platform that is detailed here.

Basically in our example two objects are created, one StringBuilder and one String.

#### StringBuilder:

The StringBuilder objects have the following memory representation.

A StringBuilder object consists of two parts (not necessarily contiguous in memory):

- First part: usage size of the array (length() of StringBuilder) and a reference to the array where the data resides.
- Second part: array size (capacity() of StringBuilder) and the array.

The array size is 16 characters plus the number of characters of the original String (“evitative”) [5]. In the picture, those 16 extra characters are shown in red, to emphasize that it is wasted memory. In Java, the characters have a size of 2 bytes. [6]

So in our example, the array will have a size of \( 2 \cdot (9 + 16) = 50 \) bytes.

In Java all objects have a *header* (if known any implementation that does not have it, let me know) in our platform the header is 12 bytes. In other popular platforms can be 8 or 16 bytes, see here [7].

Another thing to consider is the padding, which is basically a memory space that is added to meet the alignment requirement. In our case, the objects must be placed in 8-multiples memory addresses.

In summary, our StringBuilder object has the following memory size (in bytes):

First part: \( 24 \)

Second part: \( 16 + 2n + 32 + padding \) [8]

Total: \( 8(\left\lceil\dfrac{n}{4}\right\rceil + 9) \) bytes

#### String:

The String objects have the following memory representation.

A String object consists of two parts (not necessarily contiguous in memory):

- First part: reference to array (where data resides) and a hash.
- Second part: the size of the array (length() of String) and the array.

The String object here described belongs to the Java 8. In older versions of Java, the String class had more fields, therefore memory size was bigger. [7]

In summary, our String object has the following memory size (in bytes):

First part: \( 24 \)

First part: \( 16 + 2n + padding \) [8]

Total: \( 8(\left\lceil\dfrac{n}{4}\right\rceil + 5) \) bytes

#### Total memory footprint:

The total memory used by our StringBuilder and String objects is \( 16(\left\lceil\dfrac{n}{4}\right\rceil + 7) \) bytes.

In our example \( n = 9 \), so the memory used is \( 16(\left\lceil\dfrac{9}{4}\right\rceil + 7) \) bytes, which represent 160 bytes of extra memory, only to determine whether “evitative” is a palindrome or not.

Remember, these 160 bytes is a totally unnecessary memory consumption.

## Benchmarks

I was doing some benchmarks where it can be seen that the *Algorithm I* is about **8.5x** slower than Algorithms *O* and *N*.

I’m leaving out some other benchmarks that show a \( \approx 500x \) difference against *Algorithm I*.

You can see the source code of the benchmarks in my GitHub account.

The explanation of the benchmarks and the code will be pending for a future article.

*Algorithm N* versus *Algorithm O*

While previously we saw that the *Algorithm O* performs half of operations than *Algorithm N*, in the worst case; the runtime of both algorithms is affected by several factors, including: the length of the word, if the word is palindrome or not, and other factors relevant to the platform.

In many cases *Algorithm N* is faster than *Algorithm O*.

We will discuss this in a future article.

## Ultimate solution?

I believe that none of the three algorithms presented in this article represent an ultimate solution, and none of them is a Component.

A *component* should be something that can be reused and, in many cases, the algorithms described in this article are not suitable for re-use.

In addition, the three algorithms only accept a String as input. A palindrome is not just a sequence of characters that reads the same forwards and backwards. A palindrome can be found in music, in numbers and also in nature.

I am no expert in genetics, but I know that palindromes can be found in DNA strands.

Palindromes in DNA are so important that some experts consider them to be responsible for preventing the extinction of the human race (and other species too). Without palindromes in DNA, incorrigible and irreversible genetic mutations would occur, causing the extinction of the species, with the passing of generations.
In a future article we’ll talk about this topic.

## Pending issues

Replicate the *Algorithm I* in C# and analyze its efficiency in execution time and memory consumption.

## Conclusions

The *Algorithm I* is an excellent example of brevity and readability, it makes good use of abstractions available to achieve this goal. The problem with *Algorithm I* is that it is a terrible example of efficiency.

Abstractions facilitate our work, let us concentrate on the problem to be solved without having to think about the context, in this case the computer.

While abstractions are good, they have a big disadvantage. They make us forget how the machine works.

Modern programmers often abuse of abstractions and they do not have knowledge about very important things that affect the behavior of our programs, such as memory, cache, load/store buffers, branch prediction, pipelines, memory models, vector instructions (SIMD), etc …

As programmers, we must know in detail the computer, the programming language and the complexity of the components we use. Unfortunately modern programmers are just focused on things like testing, agile, metaprogramming and frameworks/libraries whose lifetime is longer than two years.

I do not want to forget to mention that the best of all abstractions was discovered by Leibniz in 1679. That abstraction is what allows us to model the real world in a computer. That abstraction is the **Bit**.

Finally, it is noteworthy that *Algorithm I* could be useful as a postcondition:

## Acknowledgements

I want to thank Mario dal Lago and Javier Velilla for reviewing the article and suggest corrections.

And finally, since we can say that *we owe our lives to palindromes*, so, a special thank to them. :)

## Notes

Byte = 8-bits.

There are architectures where 1 byte is not necessarily equivalent to 8 bits. These architectures are unusual today.
There is no standard that specifies the size of a byte, but can say that the *de facto* standard is that 1 byte = 8 bits, is most common in modern computer architectures.

#### Platform used for the analysis in this article:

- CPU
- Intel Core i7-4700MQ CPU @ 2.40GHz, Haswell
- 4 Cores, 8 Threads
- L1 Data Cache Size 4 x 32 KBytes
- L1 Instructions Cache Size 4 x 32 KBytes
- L2 Unified Cache Size 4 x 256 KBytes
- L3 Unified Cache Size 6144 KBytes

- RAM: 8192 MBytes, DDR3
- Operating System: Windows 10 Home 64-bit
- Java
- Version 1.8.0_60
- Java(TM) SE Runtime Environment (build 1.8.0_60-b27)
- 64-bit HotSpot VM.
- Compressed Oops enabled.
- Objects alignment: 8 bytes.

For analysis on other platforms, please refer to [7].

## References

[1] Zahlen means “Numbers” in German. Hence the set of integers is identified with the letter \( \mathbb{Z} \).

[2] The Art of Computer Programming Volume 1, by Donald E. Knuth [3rd Edition, page 107].

[3] Why I call String.equals() “function” and no “method”?. Here is the answer.

[4] In Java the integral data types and arrays of integral data types are initialized to 0, guaranteed by the language specification. 4.12.5 Initial Values of Variables

[7] Analysis of memory consumption on other platforms.

[8] The formulas for calculating the padding of the internal arrays of StringBuilder and String (in bytes):

StringBuilder internal array padding = \( 8\left\lceil\dfrac{2n + 48}{8}\right\rceil - (2n + 48) \)

String internal array padding = \( 8\left\lceil\dfrac{2n + 16}{8}\right\rceil - (2n + 16) \)

(These formulas are specific to the platform described in the article)

The general formula for the padding of objects is:

Share