Optimization_Concepts - AugustinLopez/libft GitHub Wiki

Some de facto standard exists regarding computer architecture, especially among personal computer, but most concepts presented here remain hardware-dependent. The libft library was developped on a x86-64 (also called x64) system: good performance are unlikely on other architecture.

Table of contents

Loop Optimization

Definition

A byte is the smallest addressable unit of memory in most modern computer architectures. It has been used historically to encode a single character of text in a computer. In the C language, it is usually associated to the unsigned char data type.

A word is the base unit of data used by a computer architectures. It is usually the largest piece of data that can be transferred to and from working memory in a single operation. The size of a word on a modern computer architecture is generally the size of a byte multiplied by a power of two.

In this library the reference values are 8-bits byte (also called an octet) and 64-bits word.

Explanation

A word is the natural unit of data in a computer: compared to a byte it can be accessed and modified without additional instruction. Any loop performed on a word-by-word basis will be about as fast as a loop performed on a byte-by-byte basis. A word loop will process more data at each iteration. Because processing a word requires additional computations, a word loop is usually less efficient with small datasets. The increase in efficiency becomes very noticiable with large datasets.

Most optimizations in the libft library consist in translating byte loops into word loops when possible.

Data Alignment

Definition

  • Data structure alignment refers to the way data is arranged and accessed in computer memory. A modern computer hardware will perform read and write operations more efficiently when the data is aligned.
  • A data is generally assumed to be aligned if its memory address is a multiple of its data size. The natural unit of memory address and data size is the byte.

In this library a word is assumed to be aligned if its memory address is a multiple of 8.

Explanation

Any data can be assumed to be byte aligned, but word alignment is not always guaranteed. Attempting to access misaligned data will result in undefined behavior.

Most optimizations based on a word loop optimization start with an alignment loop: data are first processed on a byte basis until the memory address is aligned on a word basis.

It is not uncommon that two addresses cannot be both aligned on a word basis. To optimize memory access in such scenario, data types whose size are between byte size and word size can be used, and the system endianness must be taken into account. Such optimizations introduce new edge cases and increase code size and complexity; no such implementation has been written in this library as of July 2019. In this scenario, we fall back to a byte loop.

Buffer Over-Read

Definition

  • A buffer over-read is a situation where a program overruns a buffer's boundary and attempt to read adjacent memory. A buffer over-read is a violation of of memory safety and a common cause of segmentation fault.
  • Any method used to detect if a variable is out of bounds is called bounds checking. In the C language, the result of out of bounds memory access is considered undefined behavior.

Explanation

On most computer architecture, the finer level of granularity at which a bound checking would be performed is the aligned word level. Most runtime error happens when attempting to access adjacent memory that are not on the same page. A buffer over-read will not cause problems on most architecture as long as certain conditions are met, starting with memory alignment and well defined stop condition.

String arrays are special because we rarely know their size in advance. It is likely that a word loop would read past the end of a string array into unauthorized memory, making such optimization unsafe. but the null byte marking the end of a string array must be written in a memory word. If we count on the leniency of the bound checking, we can still translate byte loop into word loop as long as we stop iterating when a null byte is found.

This concept is used extensively to optimize our string functions, but this behavior remains undefined according to the C Standard. Such optimization would be more common in the Assembly language with different paradigms in mind. See the following posts on Stackoverflow for more details: [1] [2] [3] [4] 5( https://stackoverflow.com/questions/37800739/is-it-safe-to-read-past-the-end-of-a-buffer-within-the-same-page-on-x86-and-x64 ).

Unitialized values will be read after the buffer boundary, triggering warnings from debugger such as valgrind. Those warning can be silenced with the flag --undef-value-errors=no.

Further Reading