From owner-freebsd-hackers@FreeBSD.ORG Sun Feb 15 08:42:31 2004 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id AADD816A4CE for ; Sun, 15 Feb 2004 08:42:31 -0800 (PST) Received: from mail.teleri.net (teleri.net [216.193.194.32]) by mx1.FreeBSD.org (Postfix) with ESMTP id A462343D1D for ; Sun, 15 Feb 2004 08:42:31 -0800 (PST) (envelope-from trent@teleri.net) Received: by mail.teleri.net (Postfix, from userid 1010) id 22D911144D; Sun, 15 Feb 2004 10:42:31 -0600 (CST) Date: Sun, 15 Feb 2004 08:42:31 -0800 From: Trent Nelson To: freebsd-hackers@freebsd.org Message-ID: <20040215164231.GA54709@teleri.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.1i X-Mailman-Approved-At: Mon, 16 Feb 2004 05:40:28 -0800 Subject: Branch prediction X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 15 Feb 2004 16:42:31 -0000 For as long as I've been programming, I've always been under the impression that CPUs will always predict a branch as being false the first time they come across it. Many, many years ago, I came across a DEC programming guide that said the same thing. It suggested using 'do { } while()' over 'while() {}' for loops as this ensured that the loop block was correctly pre-fetched (rather than whatever followed the loop) the first time the branch was encountered. To this day, I still write all my code in this fashion. I was wondering, have either CPU architectures or compilers improved over time such that this isn't an issue anymore? Are CPUs able to intelligently predict a branch the first time they encounter it? Do compilers re-order blocks to optimise pre-fetching and minimise branch mis-prediction? With CPUs like the P4 -- with it's 20-something stage pipeline -- branch mis-prediction is expensive. I realise certain CPUs optimise their branch prediction units by maintaining branch prediction histories, which would help when a branch is encoun- tered repeatedly, but does the old adage of "always predict false" still hold true the first time a branch is encountered? So, writing code such that the "true" branch is intended to be executed far less than what comes after it; good practice or pointless habit? Regards, Trent.