When Refactoring Fails... a^= b; b^=a; a^=b; does not swap variables.
-
Here is an interesting find-the-bug quiz. I helped code the original logic of a networked poker application. The cards were encoded as bytes (value 0 through 51) to represent each card. Part of my code created a new deck and shuffled the cards. The code worked well enough. To swap the cards when shuffling, here is the original version of the method used:
static void Swap(ref byte card1, ref byte card2) { byte temp = card1; card1 = card2; card2 = temp; return; }Then someone “refactored” a bunch of my code. They changed my Swap() method (listed above) and replace it with this popular “trick” which swaps two variables without using a temporary variable. Here is the "refactored" version:
static void Swap(ref byte card1, ref byte card2) { card1 ^= card2; card2 ^= card1; card1 ^= card2; return; }All the unit tests passed but users started getting duplicate cards. Further debug code determined that random cards were also missing from the shuffled deck. I narrowed the problem down to the refactored Swap() method. So the question is: Why doesn't the refactoring of Swap() work? Below are the original code snippets relevant to this problem. There is enough code here to compile, if you want to try it yourself. I made made everything static to simplify the code presentation. Here is the main code:
using System;
class Program
{
static void Main(string[] args)
{
byte[] deck = new byte[52]; // The deck of cards
byte[] cardCount = new byte[52]; // [debug code]: Store how many of each card is in the deck.// Create a deck with one of each card. for (byte i = 0; i < 52; i++) deck\[i\] = i; // Then shuffle them up. Shuffle(deck); // \[debug code\] Count how many of each card is in the deck. for (byte i = 0; i < deck.Length; i++) cardCount\[deck\[i\]\]++; for (byte i = 0; i < deck.Length; i++) Console.WriteLine("deck\[{0}\] appears {1} times.", i, cardCount\[i\]); }Here is the card shuffling method:
static void Shuffle(byte\[\] deck) { Random random = new Random(); // Step through each card in the deck and swap it with another random card. for (byte i = 0; i < deck.Length; i++) { byte randomCard = (byte)random.Next(deck.Length); -
Here is an interesting find-the-bug quiz. I helped code the original logic of a networked poker application. The cards were encoded as bytes (value 0 through 51) to represent each card. Part of my code created a new deck and shuffled the cards. The code worked well enough. To swap the cards when shuffling, here is the original version of the method used:
static void Swap(ref byte card1, ref byte card2) { byte temp = card1; card1 = card2; card2 = temp; return; }Then someone “refactored” a bunch of my code. They changed my Swap() method (listed above) and replace it with this popular “trick” which swaps two variables without using a temporary variable. Here is the "refactored" version:
static void Swap(ref byte card1, ref byte card2) { card1 ^= card2; card2 ^= card1; card1 ^= card2; return; }All the unit tests passed but users started getting duplicate cards. Further debug code determined that random cards were also missing from the shuffled deck. I narrowed the problem down to the refactored Swap() method. So the question is: Why doesn't the refactoring of Swap() work? Below are the original code snippets relevant to this problem. There is enough code here to compile, if you want to try it yourself. I made made everything static to simplify the code presentation. Here is the main code:
using System;
class Program
{
static void Main(string[] args)
{
byte[] deck = new byte[52]; // The deck of cards
byte[] cardCount = new byte[52]; // [debug code]: Store how many of each card is in the deck.// Create a deck with one of each card. for (byte i = 0; i < 52; i++) deck\[i\] = i; // Then shuffle them up. Shuffle(deck); // \[debug code\] Count how many of each card is in the deck. for (byte i = 0; i < deck.Length; i++) cardCount\[deck\[i\]\]++; for (byte i = 0; i < deck.Length; i++) Console.WriteLine("deck\[{0}\] appears {1} times.", i, cardCount\[i\]); }Here is the card shuffling method:
static void Shuffle(byte\[\] deck) { Random random = new Random(); // Step through each card in the deck and swap it with another random card. for (byte i = 0; i < deck.Length; i++) { byte randomCard = (byte)random.Next(deck.Length);Heh... nice one! :-) Typical example of what "optimization tricks" do to you if you don't read up on exactly in which scenarios they will fail... in this case when the references are to the same variable... right? Obviously,
i == randomCardis bound to be true now and then, and then the xor swapper fails miserably... I never ran the test, but it was only card value 0 that started popping up where it wasn't expected, wasn't it? (caveat: It's 00:53 here, and I'm still at work - brain on backup power system)Peter the small turnip
-
Heh... nice one! :-) Typical example of what "optimization tricks" do to you if you don't read up on exactly in which scenarios they will fail... in this case when the references are to the same variable... right? Obviously,
i == randomCardis bound to be true now and then, and then the xor swapper fails miserably... I never ran the test, but it was only card value 0 that started popping up where it wasn't expected, wasn't it? (caveat: It's 00:53 here, and I'm still at work - brain on backup power system)Peter the small turnip
-
Here is an interesting find-the-bug quiz. I helped code the original logic of a networked poker application. The cards were encoded as bytes (value 0 through 51) to represent each card. Part of my code created a new deck and shuffled the cards. The code worked well enough. To swap the cards when shuffling, here is the original version of the method used:
static void Swap(ref byte card1, ref byte card2) { byte temp = card1; card1 = card2; card2 = temp; return; }Then someone “refactored” a bunch of my code. They changed my Swap() method (listed above) and replace it with this popular “trick” which swaps two variables without using a temporary variable. Here is the "refactored" version:
static void Swap(ref byte card1, ref byte card2) { card1 ^= card2; card2 ^= card1; card1 ^= card2; return; }All the unit tests passed but users started getting duplicate cards. Further debug code determined that random cards were also missing from the shuffled deck. I narrowed the problem down to the refactored Swap() method. So the question is: Why doesn't the refactoring of Swap() work? Below are the original code snippets relevant to this problem. There is enough code here to compile, if you want to try it yourself. I made made everything static to simplify the code presentation. Here is the main code:
using System;
class Program
{
static void Main(string[] args)
{
byte[] deck = new byte[52]; // The deck of cards
byte[] cardCount = new byte[52]; // [debug code]: Store how many of each card is in the deck.// Create a deck with one of each card. for (byte i = 0; i < 52; i++) deck\[i\] = i; // Then shuffle them up. Shuffle(deck); // \[debug code\] Count how many of each card is in the deck. for (byte i = 0; i < deck.Length; i++) cardCount\[deck\[i\]\]++; for (byte i = 0; i < deck.Length; i++) Console.WriteLine("deck\[{0}\] appears {1} times.", i, cardCount\[i\]); }Here is the card shuffling method:
static void Shuffle(byte\[\] deck) { Random random = new Random(); // Step through each card in the deck and swap it with another random card. for (byte i = 0; i < deck.Length; i++) { byte randomCard = (byte)random.Next(deck.Length);Even if the
Swapmethod works as expected, there's another problem: theShufflemethod doesn't create a random permutation :-D
Too many passwords to remember? Try KeePass Password Safe!
-
Here is an interesting find-the-bug quiz. I helped code the original logic of a networked poker application. The cards were encoded as bytes (value 0 through 51) to represent each card. Part of my code created a new deck and shuffled the cards. The code worked well enough. To swap the cards when shuffling, here is the original version of the method used:
static void Swap(ref byte card1, ref byte card2) { byte temp = card1; card1 = card2; card2 = temp; return; }Then someone “refactored” a bunch of my code. They changed my Swap() method (listed above) and replace it with this popular “trick” which swaps two variables without using a temporary variable. Here is the "refactored" version:
static void Swap(ref byte card1, ref byte card2) { card1 ^= card2; card2 ^= card1; card1 ^= card2; return; }All the unit tests passed but users started getting duplicate cards. Further debug code determined that random cards were also missing from the shuffled deck. I narrowed the problem down to the refactored Swap() method. So the question is: Why doesn't the refactoring of Swap() work? Below are the original code snippets relevant to this problem. There is enough code here to compile, if you want to try it yourself. I made made everything static to simplify the code presentation. Here is the main code:
using System;
class Program
{
static void Main(string[] args)
{
byte[] deck = new byte[52]; // The deck of cards
byte[] cardCount = new byte[52]; // [debug code]: Store how many of each card is in the deck.// Create a deck with one of each card. for (byte i = 0; i < 52; i++) deck\[i\] = i; // Then shuffle them up. Shuffle(deck); // \[debug code\] Count how many of each card is in the deck. for (byte i = 0; i < deck.Length; i++) cardCount\[deck\[i\]\]++; for (byte i = 0; i < deck.Length; i++) Console.WriteLine("deck\[{0}\] appears {1} times.", i, cardCount\[i\]); }Here is the card shuffling method:
static void Shuffle(byte\[\] deck) { Random random = new Random(); // Step through each card in the deck and swap it with another random card. for (byte i = 0; i < deck.Length; i++) { byte randomCard = (byte)random.Next(deck.Length);It fails whenever tries to swap the same card: since the two ref variables
card1andcard2are pointing indeed to the same memory location, the firstxoroperation reset both the variables to zero (successive xors have no influence). :)If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke -
Here is an interesting find-the-bug quiz. I helped code the original logic of a networked poker application. The cards were encoded as bytes (value 0 through 51) to represent each card. Part of my code created a new deck and shuffled the cards. The code worked well enough. To swap the cards when shuffling, here is the original version of the method used:
static void Swap(ref byte card1, ref byte card2) { byte temp = card1; card1 = card2; card2 = temp; return; }Then someone “refactored” a bunch of my code. They changed my Swap() method (listed above) and replace it with this popular “trick” which swaps two variables without using a temporary variable. Here is the "refactored" version:
static void Swap(ref byte card1, ref byte card2) { card1 ^= card2; card2 ^= card1; card1 ^= card2; return; }All the unit tests passed but users started getting duplicate cards. Further debug code determined that random cards were also missing from the shuffled deck. I narrowed the problem down to the refactored Swap() method. So the question is: Why doesn't the refactoring of Swap() work? Below are the original code snippets relevant to this problem. There is enough code here to compile, if you want to try it yourself. I made made everything static to simplify the code presentation. Here is the main code:
using System;
class Program
{
static void Main(string[] args)
{
byte[] deck = new byte[52]; // The deck of cards
byte[] cardCount = new byte[52]; // [debug code]: Store how many of each card is in the deck.// Create a deck with one of each card. for (byte i = 0; i < 52; i++) deck\[i\] = i; // Then shuffle them up. Shuffle(deck); // \[debug code\] Count how many of each card is in the deck. for (byte i = 0; i < deck.Length; i++) cardCount\[deck\[i\]\]++; for (byte i = 0; i < deck.Length; i++) Console.WriteLine("deck\[{0}\] appears {1} times.", i, cardCount\[i\]); }Here is the card shuffling method:
static void Shuffle(byte\[\] deck) { Random random = new Random(); // Step through each card in the deck and swap it with another random card. for (byte i = 0; i < deck.Length; i++) { byte randomCard = (byte)random.Next(deck.Length);Robert.C.Cartaino wrote:
"refactored"
You misspelled "introduced gratuitous pseudo-optimizations". Seriously, calling that an optimization in this context is a WTF already - calling it REFACTORING is an insult. Unless you are the Bagdad Ali[^] of Software Development.
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
blog: TDD - the Aha! | Linkify!| FoldWithUs! | sighist -
Robert.C.Cartaino wrote:
"refactored"
You misspelled "introduced gratuitous pseudo-optimizations". Seriously, calling that an optimization in this context is a WTF already - calling it REFACTORING is an insult. Unless you are the Bagdad Ali[^] of Software Development.
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
blog: TDD - the Aha! | Linkify!| FoldWithUs! | sighistWell, I agree: no real optimization (moreover where optimization is not needed), no refactoring at all. But it is ingenious. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke -
Even if the
Swapmethod works as expected, there's another problem: theShufflemethod doesn't create a random permutation :-D
Too many passwords to remember? Try KeePass Password Safe!
Oh, fudge. I meant to go back and change that before I posted this. I didn't have the actual code in front of me when I started this thread so I just "winged it" to get something that would compile before I posted the sample code. The actual code-base has something more like this:
for (int i = 0; i < deck.Length; i++)
Swap(ref deck[i], ref deck[random.Next(deck.Length - i) + i]);The distribution is okay, not perfect (but that's a subject for another article).
-
Here is an interesting find-the-bug quiz. I helped code the original logic of a networked poker application. The cards were encoded as bytes (value 0 through 51) to represent each card. Part of my code created a new deck and shuffled the cards. The code worked well enough. To swap the cards when shuffling, here is the original version of the method used:
static void Swap(ref byte card1, ref byte card2) { byte temp = card1; card1 = card2; card2 = temp; return; }Then someone “refactored” a bunch of my code. They changed my Swap() method (listed above) and replace it with this popular “trick” which swaps two variables without using a temporary variable. Here is the "refactored" version:
static void Swap(ref byte card1, ref byte card2) { card1 ^= card2; card2 ^= card1; card1 ^= card2; return; }All the unit tests passed but users started getting duplicate cards. Further debug code determined that random cards were also missing from the shuffled deck. I narrowed the problem down to the refactored Swap() method. So the question is: Why doesn't the refactoring of Swap() work? Below are the original code snippets relevant to this problem. There is enough code here to compile, if you want to try it yourself. I made made everything static to simplify the code presentation. Here is the main code:
using System;
class Program
{
static void Main(string[] args)
{
byte[] deck = new byte[52]; // The deck of cards
byte[] cardCount = new byte[52]; // [debug code]: Store how many of each card is in the deck.// Create a deck with one of each card. for (byte i = 0; i < 52; i++) deck\[i\] = i; // Then shuffle them up. Shuffle(deck); // \[debug code\] Count how many of each card is in the deck. for (byte i = 0; i < deck.Length; i++) cardCount\[deck\[i\]\]++; for (byte i = 0; i < deck.Length; i++) Console.WriteLine("deck\[{0}\] appears {1} times.", i, cardCount\[i\]); }Here is the card shuffling method:
static void Shuffle(byte\[\] deck) { Random random = new Random(); // Step through each card in the deck and swap it with another random card. for (byte i = 0; i < deck.Length; i++) { byte randomCard = (byte)random.Next(deck.Length);I bet the refactorer thought they were being really clever with the XOR trick. Not clever changing working code unless you've got a really good reason. I doubt the performance would've improved much either.
