maettig.com

Thiemos Archiv

I have a collection of obsolete »computer books« from the 1980s and earlier, including many about the programming language BASIC. Whenever I skim through another addition to my collection, one BASIC keyword keeps catching my attention: SWAP. It's such a simple enhancement. There are even dedicated Wikipedia articles about the concept (Dreieckstausch in German). Yet it doesn't exist in any of the modern programming languages I use nowadays. Why is that?

History

It's not in OASIS BASIC from 1980. It is – understandably – not in the so called »MINIMAL BASIC« subset that became the rather unsuccessful ISO/IEC 6373:1984 standard, immediately obsolete when it was finally released in 1988. (By the way: A big »fuck you« to the idea of charging money for the permission to look into technical standards.)

It's not in the original C64 BASIC, but in Microsoft's BASIC version 7 that shipped with the later C128 model. It's in GFA BASIC, the dialect that was popular on the Atari ST in the 1980s and later ported to many other systems, even including Windows. It's in Microsoft's QuickBASIC since version 2.0, and in QBasic, the stripped down QuickBASIC interpreter that shipped with MS-DOS 5.0 up to 6.22 for so many years.

It's in Turbo Basic from 1987, and in the later PowerBASIC. It's in PC-BASIC. No surprise, as the rather recent language (the copyright states 2013–2018) is meant to emulate all classic BASIC dialects.

Not all modern languages miss it: There is a dedicated CPAN module for Perl called Data::Swap that can swap just everything, even variables with different types. The C++ function is named std::swap and available since C++11, but looks like it can only swap variables that both have the same type. Same for Rust, where the function is named std::mem::swap.

A theory

So why doesn't SWAP exist in popular languages like JavaScript or PHP? I have a theory. See, when was the last time you actually had to swap two variables in any of your code? See. I don't remember either. There is one place where you need it: when implementing basic algorithms like »most recently used« lists or sorting algorithms like bubble sort. It's not only convenient but essential in certain lock algorithms.

That's also the reason why SWAP is a native CPU instruction and available in assembler languages, e.g. as XCHG in x86 assembler since the original 8086 from 1978.

But we typically don't re-implement these algorithms in higher level languages. We have build-in functions to do all this, or easy to reach libraries.

However, this was different in the 1980s. BASIC neither had complex data structures nor a way to sort them. You had to do this all on your own: come up with a binary file format for whatever data you want to process, ad-hoc data structures that could hold just enough data to be useful without clogging up your precious 16 kilobytes of memory, and specialized algorithms to process it. Including, yes, sorting.

Alternatives

Ok. But still, what if I really need to swap two values in a language that doesn't have a SWAP command?

The easiest, most obvious solution is via a third, temporary variable:

temp = x;
x = y;
y = temp;

Hacks

I suggest stop reading here. Really. Just use a temporary variable. Give all variables good names, continue to refactor your code, and more often than not you will realize that you don't need this at all. But if you are a nerd like me, you want to know anyway, don't you?

When dealing with integers it's possible to use some rather funny number-crunching to swap two values:

a = a + b;
b = a - b;
a = a - b;

Similar code snippets use multiplications or XOR operations. Certainly not recommended at all because they all fail in way to many situations. Solutions using addition or multiplication can easily overflow, and fail when one value is zero. Solutions using XOR fail when both variables happen to have the same value. Pretty much all sources I found say loud and clear »don't use this, just use a temporary variable«.

Array destructuring

A much more elegant solution is possible in all languages that allow object or array destructuring (or »array deconstruction«). JavaScript can do this since ES6, which should work in all current browser versions excluding IE11:

[ a, b ] = [ b, a ];

Or using objects:

{ a, b } = { a: b, b: a };

This requires ES6 as well.

A clever variation that works in earlier versions as well looks like this:

b = [ a, a = b ][0];

This relies on a specific execution order. First, an array containing a is created, using the old value of a. Then, a is changed to contain the value from b. This becomes the second array element, but is never used again. In the end, the first array element is extracted and stored in b.

Here is the StackOverflow thread where I found this and more creative one-line solutions, and a wonderful blog post listing even more.

C# supports something called »tuples« since version 7.0 from early 2017:

(a, b) = (b, a);

PHP can do array destructuring basically since »forever«, whenever the list() keyword was introduced:

list( $a, $b ) = array( $b, $a );

The same can – thankfully – be written like this in more recent PHP versions, specifically since PHP 7.1:

[ $a, $b ] = [ $b, $a ];

This is how the same looks in languages like Python, Go, and Lua:

a, b = b, a

This looks confusing when you are not familiar with any of these languages. Explanation: The b, a piece specifies a list, and a, b deconstructs it again.

I guess that concludes my little journey for the moment. Is there anything I missed?

c++17 supports structured binding, thus no need for std::tie to do the same. Well, I´ll continue using the good ol´ swap template anyway - still most simple & specific :)

The main reason for XCHG in x86 isn´t really optimizing actual variable swaps but rather a result of lack of registers combined with specific functionality to register assignments in the first x86 revisions (pre 386), similar for FXCH for x87 with its FPU stack. On todays CPUs with out of order execution an register renaming XCHG as well as FXCH is basically a no-op anyway.
T$

Kommentare zu diesem Beitrag können per E-Mail an den Autor gesandt werden.

[ ← Zurück zur Übersicht ]

Impressum & Datenschutz