From 33391df7f217210a8017296f6bf2da8c9f60769f Mon Sep 17 00:00:00 2001 From: Stas Boukarev Date: Tue, 30 Apr 2013 23:32:43 +0400 Subject: [PATCH] Micro-optimize integer-length on fixnums on x86-64. INTEGER-LENGTH is implemented by using the BSR instruction, which returns the position of the first 1-bit from the right. And that needs to be incremented to get the width of the integer, and BSR doesn't work on 0, so it needs a branch to handle 0. But fixnums are tagged by being shifted left n-fixnum-tag-bits times, untagging by shifting right n-fixnum-tag-bits-1 times (and if n-fixnum-tag-bits = 1, no shifting is required), will make the resulting integer one bit wider, making the increment unnecessary. Then, to avoid calling BSR on 0, OR the result with 1. That sets the first bit to 1, and if all other bits are 0, BSR will return 0, which is the correct value for INTEGER-LENGTH. --- NEWS | 1 + src/compiler/x86-64/arith.lisp | 48 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 49 insertions(+) diff --git a/NEWS b/NEWS index afc31de..70a2743 100644 --- a/NEWS +++ b/NEWS @@ -10,6 +10,7 @@ changes relative to sbcl-1.1.7: sb-ext:*runtime-pathname*, sb-ext:*posix-argv* on startup, like character decoding errors, or directories being deleted. * optimization: faster ISQRT on fixnums and small bignums + * optimization: faster and smaller INTEGER-LENGTH on fixnums on x86-64. changes in sbcl-1.1.7 relative to sbcl-1.1.6: * enhancement: TRACE :PRINT-ALL handles multiple-valued forms. diff --git a/src/compiler/x86-64/arith.lisp b/src/compiler/x86-64/arith.lisp index dc33d2c..22d5bc1 100644 --- a/src/compiler/x86-64/arith.lisp +++ b/src/compiler/x86-64/arith.lisp @@ -1043,6 +1043,54 @@ constant shift greater than word length"))) (zeroize res) DONE)) +;; INTEGER-LENGTH is implemented by using the BSR instruction, which +;; returns the position of the first 1-bit from the right. And that needs +;; to be incremented to get the width of the integer, and BSR doesn't +;; work on 0, so it needs a branch to handle 0. + +;; But fixnums are tagged by being shifted left n-fixnum-tag-bits times, +;; untagging by shifting right n-fixnum-tag-bits-1 times (and if +;; n-fixnum-tag-bits = 1, no shifting is required), will make the +;; resulting integer one bit wider, making the increment unnecessary. +;; Then, to avoid calling BSR on 0, OR the result with 1. That sets the +;; first bit to 1, and if all other bits are 0, BSR will return 0, +;; which is the correct value for INTEGER-LENGTH. +(define-vop (positive-fixnum-len) + (:translate integer-length) + (:note "inline positive fixnum integer-length") + (:policy :fast-safe) + (:args (arg :scs (any-reg))) + (:arg-types positive-fixnum) + (:results (res :scs (unsigned-reg))) + (:result-types unsigned-num) + (:generator 24 + (move res arg) + (when (> n-fixnum-tag-bits 1) + (inst shr res (1- n-fixnum-tag-bits))) + (inst or res 1) + (inst bsr res res))) + +(define-vop (fixnum-len) + (:translate integer-length) + (:note "inline fixnum integer-length") + (:policy :fast-safe) + (:args (arg :scs (any-reg) :target res)) + (:arg-types tagged-num) + (:results (res :scs (unsigned-reg))) + (:result-types unsigned-num) + (:generator 25 + (move res arg) + (when (> n-fixnum-tag-bits 1) + (inst shr res (1- n-fixnum-tag-bits))) + (if (sc-is res unsigned-reg) + (inst test res res) + (inst cmp res 0)) + (inst jmp :ge POS) + (inst not res) + POS + (inst or res 1) + (inst bsr res res))) + (define-vop (unsigned-byte-64-count) (:translate logcount) (:note "inline (unsigned-byte 64) logcount") -- 1.7.10.4