12 ms·

A new fast hash table in response to Google’s new fast hash table

390 points by chewxy 8y ago

switch_kickflip 8y ago
I am essentially a hash table fetishist, and I'm a little bummed out that this doesn't go into more detail about how the damn thing works. How do you do implement a chaining hash table that uses a single flat array?
- wichert 8y ago
  You can look at the source in his github repository: https://github.com/skarupke/flat_hash_map https://github.com/skarupke/flat_hash_map
  - dividuum 8y ago
    That's not the same as having a high level description of the concepts used. For details I can still dive into the details later.
  - titzer 8y ago
    I looked through the code and o_O there is a lot of C++ boilerplate. The core part of it is not really documented well, and there is this mysterious jump bits array...if I had more time, I could figure out it. But that's the point of a writeup, explaining things with a diagram, etc.
    - Tomis02 8y ago
      To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
    - jcelerier 8y ago
      > I looked through the code and o_O there is a lot of C++ boilerplate. This boilerplate allows me to choose between std::unordered_map and flat_hash_map in my whole code just by toggling a compile time switch in my code. It ensures that the data structures has the same API than all other C++ containers.
      - titzer 8y ago
        I understand what it is for. YMMV but for me C++ is pretty much a constant mental stack overflow when reading the guts like this. It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here.
        jcelerier 8y ago
        > It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here. well, I mean... if it was not configurable, it would not really be useful, except for toy examples, and for those the default std::unordered_map is more than sufficient. To be useful, a hash table implementation at least needs to allow to configure the hash function and the comparison operator.
        kwillets 8y ago
        I actually have separate implementations of an algorithm with and without templates; the template one is for benchmarking with different combinations of options; the non-template one is for readability, and it's only about 60 lines.
- lentil_soup 8y ago
  He mentions he'll update the blog post with a link to the talk he gave once it's online
- andromeduck 8y ago
  Like a FAT format but with relative indices. It should be pretty trivial pointer arithmetic. Edit: bytell_hash_map.cpp:464 bytell_hash_map.cpp:58 Apparently there's one extra layer of indirection via a lookup table to get the final offset. So basically the metadata byte is a bitfield union of + status flag + status code (not sure it's actually required) or offset enum. The offset enum then indexes into a look up table, the result of which is the relative offset from the current index.
- redcalx 8y ago
  You do hash % bucketCount to find your bucket/slot. Each array element is also a linked list node (with a next pointer), thus if the slot is populated you follow the linked list until an empty slot is found and attach to the end of the linked list. I figure it works best if you over allocate slots, so that on average you only have to do very few hops on each linked list walk (or no walk at all). Aside: This is the method employed by .NET's Dictionary<K,V> class. Further - it's generally faster to use structure of arrays rather than array of structures, thus in the above scheme the dictionary items/payloads and the linked list pointers could be in separate arrays.
masklinn 8y ago
Would be interesting to have comparisons with Rust's std hashmap and indexmap (formerly ordermap) as well.
ilija139 8y ago
I wonder how it compares to Google's "Learned Index Structures" https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/1712.01208
- koverstreet 8y ago
  Completely different - that paper applies to comparison based indexing.
- stochastic_monk 8y ago
  I don’t think there’s much to write home about RE: Learned Index Structures since classical structures can soundly outperform at least the trumpeted Google “success story” [1]. It’s hype, not substance. [1]: https://dawn.cs.stanford.edu/2018/01/11/index-baselines/ https://dawn.cs.stanford.edu/2018/01/11/index-baselines/
  - jacksmith21006 8y ago
    Completely disagree. It is NOT simply about the results but looking at the direction and a new approach. Ultimately it also comes down to the power required to get some task done. Also how can a paper submitted to NIPS be hype?
    - stochastic_monk 8y ago
      As an idea and an application of machine learning, it’s important and worth exploring. Claiming it’s better is false. That’s a distinction worth making.
- jacksmith21006 8y ago
  Great link. I will be curious to see if the Google, Jeff Dean, approach works in real life situations. What is interesting is you can use the TPUs and parallelize the approach. Ultimately it is about using less power to get some work done.
zawerf 8y ago
Sort of off topic: In theory hash tables are supposed to be O(1) (under the RAM model). But looking at these graphs, they seem to grow linearly after they stop fitting in the cache which is especially apparent on the unsuccessful lookup graph. Since it's on a log-scale graph, O(log(n)) would probably fit better. Just thought it's an interesting divergence between what's taught in school and in practice. I wonder if there's something that's more predictive than big Oh for these types of analysis.
- adrianN 8y ago
  You just need to use a machine model that takes into account the cost of address translation and the TLB. Check out https://arxiv.org/abs/1212.0703 https://arxiv.org/abs/1212.0703 for some introduction to the topic.
- dspillett 8y ago
  > divergence between what's taught in school and in practice I remember this sort of thing being mentioned but not in as much detail as I would have gone into (though I'd self-taught a lot of this before Uni, so for me it was more an exercise in unlearning mistakes and formalising & rounding off knowledge than it was about taking in new concepts, perhaps for others cramming the extra detail in would have been counter productive). Algorithm courses would say things like "of course caching methods should be taking into consideration, you'll cover this in architecture modules" and architecture modules would say "you'll cover the effect on some algorithms in much more detail in your software engineering modules"! All the JS sorting demos that were an active fad a short while ago were simplified in the same way: they assumed that either a comparison or a swap was always the most expensive operation and the other can be discounted, or that all swaps/comparisons are equal due to uniform memory speed (no accounting for caching), and no consideration was made for what was being sorted (inserts are much more expensive in an array than a linked list for instance). I keep meaning to find the time to put a less superficial demo together that allows such things to be modelled at a basic level, perhaps even trying to illustrate the effect of a more distributed architecture (where there is more than one processing unit involved and everything isn't in local fast memory). Of course, for the most part these simplifications are perfectly valid, but they should always carry a caveat noting what simplifying assumptions are being applied so people learning know that the issues could be more complicated so some critical thinking should be applied in any real world situation.
antirez 8y ago
Does this implementation stops on rehashing? We should stop considering seriously hash tables that stop for rehashing because they can be used only for a subset of problems, due to the latency. This is one of the main reasons I'm now in love with radix trees and trying to get rid of hash tables at every level in my code.
- MaxBarraclough 8y ago
  Are radix trees always better? I doubt it.
  - thecompilr 8y ago
    Depending on implementation and usage, radix trees can get extremely segmented, slowing down significantly over time.
    - ztorkelson 8y ago
      Would you mind elaborating? I'm not quite sure what you mean by segmented here.
      - MaxBarraclough 8y ago
        I'm not thecompilr, but if I understand them correctly: In the worst case, the cache behaviour of a radix tree could be awful, if each node lives in a different cache-line, no? I imagine this problem can be ameliorated with a custom allocator, though. Been a while since I've studied hash-maps in depth, but with a good hash function, that wouldn't be a big worry, would it?
        ztorkelson 8y ago
        Gotcha. Yes, while there are implementation techniques that can help (e.g. arena allocation, prefix compression, adaptive node sizes), the data structure is fundamentally a tree, and so one can expect a higher number of random memory accesses (when compared with suitably optimized hash tables, like those discussed in the article). In some scenarios, radix trees can overcome that with better space efficiency (i.e. implicit key storage), but I think it's fair to say that there are many scenarios (if not most!) where hash tables outperform radix trees. Of course, that all hinges on how you measure performance. As Salvatore pointed out, if you're looking to minimize variance, hash tables might not be suitable due to their growth characteristics. Radix trees also give you efficient sorting and range scans out of the box, and are a viable immutable persistent data structure as well. If none of those are meaningful to your use cases, then hash tables could certainly be a better fit.
tniemi 8y ago
I personally prefer Judy arrays: http://judy.sourceforge.net/ http://judy.sourceforge.net/
- MaxBarraclough 8y ago
  From http://judy.sourceforge.net/doc/10minutes.htm http://judy.sourceforge.net/doc/10minutes.htm : > From a speed point of view Judy is chiefly a 256-ary digital tree or trie (per D. Knuth Volume 3 definitions). A degree of 256-ary is a somewhat "magic" N-ary for a variety of reasons -- but mostly because a byte (the least addressable memory unit) is 8 bits. Also a higher degree means reduced cache-line fills per access. You see the theme here -- avoid cache-line fills like the plague. Sounds like a neat data-structure made with cache behaviour in mind. I'm not getting much out of the creator's attempts to explain it, but there's a Wikipedia article: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array
ebikelaw 8y ago
Wheres the source of this newer Google table? Can not find it nor the announcement of it.
- utopcell 8y ago
  It is not open sourced yet but a presentation was given in cppcon17
  - utopcell 8y ago
    Here: https://m.youtube.com/watch?v=ncHmEUmJZf4 https://m.youtube.com/watch?v=ncHmEUmJZf4 Recommended watch. Matt is a fun presenter.
  - ebikelaw 8y ago
    But ... how does it appear in the benchmarks of this article?
    - Arcuru 8y ago
      The author claims to have written an implementation of it themselves. From the article: > This last one is my implementation of Google’s new hash table. Google hasn’t open-sourced their hash table yet, so I had to implement their hash table myself. I’m 95% sure that I got their performance right.
utopcell 8y ago
I like this work. We should be seeing more exploratory posts like this one. I find it interesting that both google's and skarupke@'s hash map have exactly the same name: flat_hash_map. Maybe boost-inspired ?
jbapple 8y ago
This post has some overconfident and under-researched claims: > This came about because last year I wrote the fastest hash table (I still make that claim) I'm extremely dubious of claims of the "fastest $DATA_STRUCTURE" without qualifiers about workload, hardware, and time/space trade-off. In particular, the last graph of this post shows some workloads (400k int keys, int[16] values, unsuccessful lookups) where the author's implementation of Swiss Table (as Google called their table) is 3x-10x slower than "bytell_hash_map", the author's own design. > google_flat16_hash_map. This last one is my implementation of Google’s new hash table. Google hasn’t open-sourced their hash table yet, so I had to implement their hash table myself. I’m 95% sure that I got their performance right. The talk announcing Swiss Table clearly didn't have enough detail to fully replicate their results. This 95% claim is rather astonishing in light of that.
- coconutrandom 8y ago
  meta: classic HN, top post is a Negative Nancy regardless of how impressive the new thing is. Is there a name for this phenomena yet?
  - hobofan 8y ago
    "Critical thinking"?
  - vanderZwan 8y ago
    I know the type of post you talk about - dismissive easy critiques like "correlation does not.." - but GP's remark is not quite like that: - it states the article has some overconfident claims. - it gives detailed arguments for why > Is there a name for this phenomena yet? "bachelors' wives and maidens' children are well taught"?
  - nabla9 8y ago
    No and there should not be. There unjustified critique and justified critique. ´
  - newnewpdro 8y ago
    A healthy dose of skepticism
program_whiz 8y ago
Props, this is an amazing contribution. So much respect for someone who can really dig in, figure this stuff out, and make a better data-structure for nothing more than the love of doing so. Everyone making their living as a programmer/tech person owes it to people like this who make the basic tools.
- utopcell 8y ago
  To be fair, the max load factor for this hash map is set to 0.5, which is quite wasteful in terms of memory. If you allow for 50% load in dense_hash_map (and most hash maps for that matter,) they become much faster themselves.
  - SolarNet 8y ago
    The hashmap the author wrote is .95, it's the google ones with a 0.5 load factor.
    - utopcell 8y ago
      Is this true? From the article: ''ska::flat_hash_map has a max_load_factor of 0.5''. ska::flat_hash_map is the author's implementation (but maybe not the most recent iteration ?)
      - jpetso 8y ago
        Right, ska::bytell_hash_map is the most recent iteration and ska::flat_hash_map was the previous one.
- vanderZwan 8y ago
  His ska-sort (a really fast in-place radix sort generalisable to almost all data) is also very interesting, I'm surprised there aren't more people working on the data structures he builds to make little improvements. I may actually have figured out a way to (theoretically) make it faster, but I don't grok C++ templates so can't write a pull-request (the general idea is: instead of a standard full swap, use two temporaries and ping-pong between them while swapping elements to do half-swaps. This reduces required assignments to move an element to its final position from three to two).

390 points by chewxy 8y ago

I am essentially a hash table fetishist, and I'm a little bummed out that this doesn't go into more detail about how the damn thing works. How do you do implement a chaining hash table that uses a single flat array?

wichert 8y ago
You can look at the source in his github repository: https://github.com/skarupke/flat_hash_map https://github.com/skarupke/flat_hash_map
- dividuum 8y ago
  That's not the same as having a high level description of the concepts used. For details I can still dive into the details later.
- titzer 8y ago
  I looked through the code and o_O there is a lot of C++ boilerplate. The core part of it is not really documented well, and there is this mysterious jump bits array...if I had more time, I could figure out it. But that's the point of a writeup, explaining things with a diagram, etc.
  - Tomis02 8y ago
    To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
  - jcelerier 8y ago
    > I looked through the code and o_O there is a lot of C++ boilerplate. This boilerplate allows me to choose between std::unordered_map and flat_hash_map in my whole code just by toggling a compile time switch in my code. It ensures that the data structures has the same API than all other C++ containers.
    - titzer 8y ago
      I understand what it is for. YMMV but for me C++ is pretty much a constant mental stack overflow when reading the guts like this. It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here.
      - jcelerier 8y ago
        > It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here. well, I mean... if it was not configurable, it would not really be useful, except for toy examples, and for those the default std::unordered_map is more than sufficient. To be useful, a hash table implementation at least needs to allow to configure the hash function and the comparison operator.
      - kwillets 8y ago
        I actually have separate implementations of an algorithm with and without templates; the template one is for benchmarking with different combinations of options; the non-template one is for readability, and it's only about 60 lines.
lentil_soup 8y ago
He mentions he'll update the blog post with a link to the talk he gave once it's online
andromeduck 8y ago
Like a FAT format but with relative indices. It should be pretty trivial pointer arithmetic. Edit: bytell_hash_map.cpp:464 bytell_hash_map.cpp:58 Apparently there's one extra layer of indirection via a lookup table to get the final offset. So basically the metadata byte is a bitfield union of + status flag + status code (not sure it's actually required) or offset enum. The offset enum then indexes into a look up table, the result of which is the relative offset from the current index.
redcalx 8y ago
You do hash % bucketCount to find your bucket/slot. Each array element is also a linked list node (with a next pointer), thus if the slot is populated you follow the linked list until an empty slot is found and attach to the end of the linked list. I figure it works best if you over allocate slots, so that on average you only have to do very few hops on each linked list walk (or no walk at all). Aside: This is the method employed by .NET's Dictionary<K,V> class. Further - it's generally faster to use structure of arrays rather than array of structures, thus in the above scheme the dictionary items/payloads and the linked list pointers could be in separate arrays.

masklinn 8y ago

Would be interesting to have comparisons with Rust's std hashmap and indexmap (formerly ordermap) as well.

ilija139 8y ago

I wonder how it compares to Google's "Learned Index Structures" https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/1712.01208

koverstreet 8y ago
Completely different - that paper applies to comparison based indexing.
stochastic_monk 8y ago
I don’t think there’s much to write home about RE: Learned Index Structures since classical structures can soundly outperform at least the trumpeted Google “success story” [1]. It’s hype, not substance. [1]: https://dawn.cs.stanford.edu/2018/01/11/index-baselines/ https://dawn.cs.stanford.edu/2018/01/11/index-baselines/
- jacksmith21006 8y ago
  Completely disagree. It is NOT simply about the results but looking at the direction and a new approach. Ultimately it also comes down to the power required to get some task done. Also how can a paper submitted to NIPS be hype?
  - stochastic_monk 8y ago
    As an idea and an application of machine learning, it’s important and worth exploring. Claiming it’s better is false. That’s a distinction worth making.
jacksmith21006 8y ago
Great link. I will be curious to see if the Google, Jeff Dean, approach works in real life situations. What is interesting is you can use the TPUs and parallelize the approach. Ultimately it is about using less power to get some work done.

zawerf 8y ago

Sort of off topic: In theory hash tables are supposed to be O(1) (under the RAM model). But looking at these graphs, they seem to grow linearly after they stop fitting in the cache which is especially apparent on the unsuccessful lookup graph. Since it's on a log-scale graph, O(log(n)) would probably fit better. Just thought it's an interesting divergence between what's taught in school and in practice. I wonder if there's something that's more predictive than big Oh for these types of analysis.

adrianN 8y ago
You just need to use a machine model that takes into account the cost of address translation and the TLB. Check out https://arxiv.org/abs/1212.0703 https://arxiv.org/abs/1212.0703 for some introduction to the topic.
dspillett 8y ago
> divergence between what's taught in school and in practice I remember this sort of thing being mentioned but not in as much detail as I would have gone into (though I'd self-taught a lot of this before Uni, so for me it was more an exercise in unlearning mistakes and formalising & rounding off knowledge than it was about taking in new concepts, perhaps for others cramming the extra detail in would have been counter productive). Algorithm courses would say things like "of course caching methods should be taking into consideration, you'll cover this in architecture modules" and architecture modules would say "you'll cover the effect on some algorithms in much more detail in your software engineering modules"! All the JS sorting demos that were an active fad a short while ago were simplified in the same way: they assumed that either a comparison or a swap was always the most expensive operation and the other can be discounted, or that all swaps/comparisons are equal due to uniform memory speed (no accounting for caching), and no consideration was made for what was being sorted (inserts are much more expensive in an array than a linked list for instance). I keep meaning to find the time to put a less superficial demo together that allows such things to be modelled at a basic level, perhaps even trying to illustrate the effect of a more distributed architecture (where there is more than one processing unit involved and everything isn't in local fast memory). Of course, for the most part these simplifications are perfectly valid, but they should always carry a caveat noting what simplifying assumptions are being applied so people learning know that the issues could be more complicated so some critical thinking should be applied in any real world situation.

antirez 8y ago

Does this implementation stops on rehashing? We should stop considering seriously hash tables that stop for rehashing because they can be used only for a subset of problems, due to the latency. This is one of the main reasons I'm now in love with radix trees and trying to get rid of hash tables at every level in my code.

MaxBarraclough 8y ago
Are radix trees always better? I doubt it.
- thecompilr 8y ago
  Depending on implementation and usage, radix trees can get extremely segmented, slowing down significantly over time.
  - ztorkelson 8y ago
    Would you mind elaborating? I'm not quite sure what you mean by segmented here.
    - MaxBarraclough 8y ago
      I'm not thecompilr, but if I understand them correctly: In the worst case, the cache behaviour of a radix tree could be awful, if each node lives in a different cache-line, no? I imagine this problem can be ameliorated with a custom allocator, though. Been a while since I've studied hash-maps in depth, but with a good hash function, that wouldn't be a big worry, would it?
      - ztorkelson 8y ago
        Gotcha. Yes, while there are implementation techniques that can help (e.g. arena allocation, prefix compression, adaptive node sizes), the data structure is fundamentally a tree, and so one can expect a higher number of random memory accesses (when compared with suitably optimized hash tables, like those discussed in the article). In some scenarios, radix trees can overcome that with better space efficiency (i.e. implicit key storage), but I think it's fair to say that there are many scenarios (if not most!) where hash tables outperform radix trees. Of course, that all hinges on how you measure performance. As Salvatore pointed out, if you're looking to minimize variance, hash tables might not be suitable due to their growth characteristics. Radix trees also give you efficient sorting and range scans out of the box, and are a viable immutable persistent data structure as well. If none of those are meaningful to your use cases, then hash tables could certainly be a better fit.

tniemi 8y ago

I personally prefer Judy arrays: http://judy.sourceforge.net/ http://judy.sourceforge.net/

MaxBarraclough 8y ago
From http://judy.sourceforge.net/doc/10minutes.htm http://judy.sourceforge.net/doc/10minutes.htm : > From a speed point of view Judy is chiefly a 256-ary digital tree or trie (per D. Knuth Volume 3 definitions). A degree of 256-ary is a somewhat "magic" N-ary for a variety of reasons -- but mostly because a byte (the least addressable memory unit) is 8 bits. Also a higher degree means reduced cache-line fills per access. You see the theme here -- avoid cache-line fills like the plague. Sounds like a neat data-structure made with cache behaviour in mind. I'm not getting much out of the creator's attempts to explain it, but there's a Wikipedia article: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array

ebikelaw 8y ago

Wheres the source of this newer Google table? Can not find it nor the announcement of it.

utopcell 8y ago
It is not open sourced yet but a presentation was given in cppcon17
- utopcell 8y ago
  Here: https://m.youtube.com/watch?v=ncHmEUmJZf4 https://m.youtube.com/watch?v=ncHmEUmJZf4 Recommended watch. Matt is a fun presenter.
- ebikelaw 8y ago
  But ... how does it appear in the benchmarks of this article?
  - Arcuru 8y ago
    The author claims to have written an implementation of it themselves. From the article: > This last one is my implementation of Google’s new hash table. Google hasn’t open-sourced their hash table yet, so I had to implement their hash table myself. I’m 95% sure that I got their performance right.

utopcell 8y ago

I like this work. We should be seeing more exploratory posts like this one. I find it interesting that both google's and skarupke@'s hash map have exactly the same name: flat_hash_map. Maybe boost-inspired ?

jbapple 8y ago

This post has some overconfident and under-researched claims: > This came about because last year I wrote the fastest hash table (I still make that claim) I'm extremely dubious of claims of the "fastest $DATA_STRUCTURE" without qualifiers about workload, hardware, and time/space trade-off. In particular, the last graph of this post shows some workloads (400k int keys, int[16] values, unsuccessful lookups) where the author's implementation of Swiss Table (as Google called their table) is 3x-10x slower than "bytell_hash_map", the author's own design. > google_flat16_hash_map. This last one is my implementation of Google’s new hash table. Google hasn’t open-sourced their hash table yet, so I had to implement their hash table myself. I’m 95% sure that I got their performance right. The talk announcing Swiss Table clearly didn't have enough detail to fully replicate their results. This 95% claim is rather astonishing in light of that.

coconutrandom 8y ago
meta: classic HN, top post is a Negative Nancy regardless of how impressive the new thing is. Is there a name for this phenomena yet?
- hobofan 8y ago
  "Critical thinking"?
- vanderZwan 8y ago
  I know the type of post you talk about - dismissive easy critiques like "correlation does not.." - but GP's remark is not quite like that: - it states the article has some overconfident claims. - it gives detailed arguments for why > Is there a name for this phenomena yet? "bachelors' wives and maidens' children are well taught"?
- nabla9 8y ago
  No and there should not be. There unjustified critique and justified critique. ´
- newnewpdro 8y ago
  A healthy dose of skepticism

program_whiz 8y ago

Props, this is an amazing contribution. So much respect for someone who can really dig in, figure this stuff out, and make a better data-structure for nothing more than the love of doing so. Everyone making their living as a programmer/tech person owes it to people like this who make the basic tools.

utopcell 8y ago
To be fair, the max load factor for this hash map is set to 0.5, which is quite wasteful in terms of memory. If you allow for 50% load in dense_hash_map (and most hash maps for that matter,) they become much faster themselves.
- SolarNet 8y ago
  The hashmap the author wrote is .95, it's the google ones with a 0.5 load factor.
  - utopcell 8y ago
    Is this true? From the article: ''ska::flat_hash_map has a max_load_factor of 0.5''. ska::flat_hash_map is the author's implementation (but maybe not the most recent iteration ?)
    - jpetso 8y ago
      Right, ska::bytell_hash_map is the most recent iteration and ska::flat_hash_map was the previous one.
vanderZwan 8y ago
His ska-sort (a really fast in-place radix sort generalisable to almost all data) is also very interesting, I'm surprised there aren't more people working on the data structures he builds to make little improvements. I may actually have figured out a way to (theoretically) make it faster, but I don't grok C++ templates so can't write a pull-request (the general idea is: instead of a standard full swap, use two temporaries and ping-pong between them while swapping elements to do half-swaps. This reduces required assignments to move an element to its final position from three to two).