/* Hi, this program simulates dynamic branch prediction. Branch prediction is used by modern processors to optimize branching instructions, like if statements and for loops. The processor keeps track of previous executions of these instructions to base its guess on so that it can preload other instructions to its pipeline. If the processor guesses correctly, it doesn't have to do anything else and it can keep going, saving speed it would otherwise waste waiting for the branching instruction. If the processor guesses incorrectly it has to halt, roll back, and go the other direction. As you can guess this is more expensive than just waiting. Almost as much as the cost of a division. It's to the programmer to layout your code in such a way so that most common branches are placed first in your code and the more random ones last. This program hopefully makes you aware of this. ( Not taking global predictions into account; branching optimization based on other instructions ) Consider a branch like if( true ) or if( false ), both of these branching instructions have a 100% chance to go in 1 direction. So the processor can always guess correctly. ( assuming no optimization by the compiler ) int random = flipcoin(); // assuming flipcoin has a 50% chance to return heads(1) or tails(0) if( random == 0 ) now this branching instruction has a 50% chance to go in either direction. The processor will have a very hard time guessing the direction correctly and will definitely slow your program down quite a bit. char c; std::cin >> c; if( c == '0' ) here it entirely depends on the user what the chance is. A user that continuously spams '0' will increase the likely hood in the 100% direction that 1 specific direction is preloaded. random input would also have a higher chance to go to 1 specific direction because what are the chances you get a '0'? ( assuming many values are possible ) But if the 'random' possible inputs are either a '0' or a '1' then we go back to the flipcoin example. Output of the program will be in the format: Line 1: ...

... ... <% that the branch is taken> Line 2: ... As the output will demonstrate, the more random the branching becomes, the worse the algorithm functions. Values towards 100 or 0 will have a much higher success rate. Values towards 50 are basically random guesses at that point. If you want to read more about branching, check out: https://en.wikipedia.org/wiki/Branch_predictor https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array */ #include #include #include #include #include #include // Returns number of clock cycles of the cpu, used to seed random number generator uint64_t rdtsc() { uint32_t l, h; __asm__ __volatile__( "rdtsc" : "=a"(l), "=d"(h) ); return (uint64_t)h << 32 | l; } // Utility class class Random { public: template static T getRandom( T min, T max ); private: static std::mt19937 m_mt; }; std::mt19937 Random::m_mt( rdtsc() ); template T Random::getRandom( T min, T max ) { static_assert( std::is_integral() || std::is_floating_point(), "T must either be an integral or a floating point!"); return typename std::conditional< std::is_integral::value, std::uniform_int_distribution, std::uniform_real_distribution >::type( min, max )( m_mt ); } /* BranchTableSize = Size of the branching table NBit is used to represent the number of bits the saturating counter uses. The counter counts up or down depending on whether its prediction is correct. 1 Bit saturation: 0 No jump 1 Jump 2 Bit saturation <-- works best 00 No jump 01 No jump 10 Jump 11 Jump 3 Bit saturation 000 No jump 001 No jump 010 No jump 011 No jump 100 jump 101 jump 110 jump 111 jump etc... */ template class BranchPredictor { static_assert( BranchTableSize > 1, "BranchTableSize must be bigger than 1!" ); static_assert( NBit > 0, "Number of bits must be bigger than 0!" ); public: BranchPredictor( unsigned numberOfBranches ); void guessBranching(); void displayBranches() const noexcept; private: struct Branch { uintptr_t address; // Location of the branching instruction uintptr_t jump_address; // Location the branching instruction jumps to double probability; // Just for simulation purposes, this is the odds the branch will be taken friend bool operator==( const Branch& lhs, const Branch& rhs ) { return lhs.address == rhs.address; } friend bool operator<( const Branch& lhs, const Branch& rhs ) { return lhs.address < rhs.address; } }; // Used to keep track of the stats while simulating struct Stats { unsigned number_of_guesses; unsigned number_of_correct_guesses; }; // The branch prediction table struct struct BranchTableEntry { const Branch* branch; int saturating_counter; // This keeps track of the counter, used to make the actual guess. Stats stats; }; private: // All branches are stored here for simulation purposes std::vector m_BranchAddresses; // The actual container for all branch entries and prediction data std::array m_BranchPredictionTable; }; template BranchPredictor::BranchPredictor( unsigned numberOfBranches ) { // Can't exceed the size of the table numberOfBranches = std::min( numberOfBranches, BranchTableSize ); m_BranchAddresses.reserve( numberOfBranches ); auto generator = [this]() -> Branch { return { Random::getRandom( (uintptr_t)this, (uintptr_t)this + BranchTableSize - 1 ), Random::getRandom( (uintptr_t)this, (uintptr_t)this + BranchTableSize * 128 - 1 ), Random::getRandom( 0.0, 1.0 ) }; }; std::generate_n( std::back_inserter( m_BranchAddresses ), numberOfBranches, generator ); std::sort( m_BranchAddresses.begin(), m_BranchAddresses.end() ); // Too lazy to make a unique random number generator atm, so I'll just erase duplicates :) m_BranchAddresses.erase( std::unique( m_BranchAddresses.begin(), m_BranchAddresses.end() ), m_BranchAddresses.end() ); // zero out m_BranchPredictionTable. std::array is an aggregate containing aggregates, so it's fine memset( &m_BranchPredictionTable, 0, sizeof( m_BranchPredictionTable ) ); } template void BranchPredictor::guessBranching() { for( const auto& i : m_BranchAddresses ) { // At this point the branch prediction could cache in the correct section for the cpu to save time // Generate a number to see if the branch will be taken double r = Random::getRandom( 0.0, 1.0 ); // Would the jump be taken? bool jump = r && r <= i.probability; // Get the correct table entry, gotta be O(1) auto& table_entry = m_BranchPredictionTable[ i.address % BranchTableSize ]; bool first_entry = table_entry.branch == nullptr; if( jump && first_entry ) // New branch detected, add it { // Only add a new branch when a jump IS taken AND no entry exists yet. // Save the branch instruction table_entry.branch = &i; // Start the guess at yes, the branch will be taken table_entry.saturating_counter = (1 << NBit) / 2; table_entry.stats.number_of_guesses = 0; table_entry.stats.number_of_correct_guesses = 0; } else if( !first_entry ) { // The branch is in the prediction table, so check if its guess is correct and update the table accordingly // Check if the counter is above a certain threshold bool branch_guess = table_entry.saturating_counter >= (1 << NBit) / 2; // 1 is predict yes, 0 is predict no if( branch_guess == jump ) { // The prediction was correct, add to the counter( no predictions count down, yes count up ) table_entry.saturating_counter += branch_guess ? 1 : -1; table_entry.stats.number_of_correct_guesses++; // Code can keep going in the real deal } else { // The prediction was incorrect, subtract from the counter( no predictions count up, yes count down ) table_entry.saturating_counter -= branch_guess ? 1 : -1; // Code has to halt, roll back and take the other path, you want this to be as low as possible } // Clamp the counter if( table_entry.saturating_counter < 0 ) table_entry.saturating_counter = 0; else if( table_entry.saturating_counter >= 1 << NBit ) table_entry.saturating_counter = (1 << NBit) - 1; // Add to the number of guesses performed table_entry.stats.number_of_guesses++; } else { // ignored if jump was false and not yet added to the prediction table } } } template void BranchPredictor::displayBranches() const noexcept { for( const auto& i : m_BranchAddresses ) { Stats stats = m_BranchPredictionTable[i.address % BranchTableSize].stats; double error = (stats.number_of_guesses ? static_cast( stats.number_of_correct_guesses ) / stats.number_of_guesses : 1.0); std::cout << "Jump from 0x" << std::hex << i.address << " to 0x" << i.jump_address << std::dec << " Trigger percentage: " << i.probability * 100 << "%" << "\nNumber of correct predictions: " << error * 100 << "%\n\n"; } } int main() { BranchPredictor<1024, 2> bp( 30 ); for( int i = 0; i < 5000; ++i ) bp.guessBranching(); std::cout << "Output of the program will be in the format:\n" << "Line 1:

<% that the branch is taken>\n" << "Line 2: \n\n"; bp.displayBranches(); }

Branch predictor