From: Emre Sevinc
Subject: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <87wtbv7b2t.fsf@ileriseviye.org>
Maybe some of you have already heard about that BinarySearch bug:
Extra, Extra - Read All About It: Nearly All Binary Searches
and Mergesorts are Broken:
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
When I've talked about that in public techno forum 2 groups of
reactions formed:
- Java programmers' reactions were something like, "come on,
we're talking about a bug that reveals itself in a binary search
operation that takes roughly 1 billion elements! Is that your
typical daily array size? It may be for a Google programmer, but...
So either roll your own binary search function, use IBM's or BEA's
JVM, or wait it to be fixed for Mustang (or backported).
- People who did some CL, Scheme, Python etc. reacted: Why
try to solve a problem instead of using a language that didn't
introduce the problem at all?
The reaction was simple: "So go and try to write your binary
search in CL that does operations on an array having at least
1 billion elements."
So my question's audience are people who had both CL and Java
experience:
What if you were trying to write a binary search? You'd
have a platform that didn't indroduce such a bug but
what kind of a performance would it have (with a 1 billion
element array)? What would you value and why? Correctness
and being bug-free or having potential bugs but not
worry and think, "that's an extreme case and my typical
application stuff never goes to those extremes anyway."?
Regards,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http://emba.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Peter Seibel
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <m24pyzh3a8.fsf@gigamonkeys.com>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Maybe some of you have already heard about that BinarySearch bug:
>
> Extra, Extra - Read All About It: Nearly All Binary Searches
> and Mergesorts are Broken:
>
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
>
> When I've talked about that in public techno forum 2 groups of
> reactions formed:
>
> - Java programmers' reactions were something like, "come on,
> we're talking about a bug that reveals itself in a binary search
> operation that takes roughly 1 billion elements! Is that your
> typical daily array size? It may be for a Google programmer, but...
> So either roll your own binary search function, use IBM's or BEA's
> JVM, or wait it to be fixed for Mustang (or backported).
>
> - People who did some CL, Scheme, Python etc. reacted: Why
> try to solve a problem instead of using a language that didn't
> introduce the problem at all?
>
> The reaction was simple: "So go and try to write your binary
> search in CL that does operations on an array having at least
> 1 billion elements."
>
> So my question's audience are people who had both CL and Java
> experience:
>
> What if you were trying to write a binary search? You'd
> have a platform that didn't indroduce such a bug but
> what kind of a performance would it have (with a 1 billion
> element array)? What would you value and why? Correctness
> and being bug-free or having potential bugs but not
> worry and think, "that's an extreme case and my typical
> application stuff never goes to those extremes anyway."?
In this case it seems silly not to just write it "correctly". I'm not
going to worry that
(+ low (floor (- high low) 2))
is potentially a couple cycles slower than:
(floor (+ low high) 2)
when the whole point of a binary search is that this computation is
only done log N times.
-Peter
P.S. In fact in a binary search code that I wrote recently, that's how
I wrote it, probably because I was thinking about the fact that I had
declared low and high to be fixnum and didn't want the compiler to
have to switch over to non-fixnum math to sum them.
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Emre Sevinc wrote:
> What if you were trying to write a binary search? You'd
> have a platform that didn't indroduce such a bug but
> what kind of a performance would it have (with a 1 billion
> element array)? What would you value and why? Correctness
> and being bug-free or having potential bugs but not
> worry and think, "that's an extreme case and my typical
> application stuff never goes to those extremes anyway."?
As you wrote, in CL this is not a problem, because the index is automaticly
adjusted to bignums, if it doesn't fit anymore in a fixnum. So if you are
lucky and your CL implemenations provides an array-dimension-limit > 1e9,
there should be no problem. Speed is not critical, because for 1e9 elements
you need at most 30 steps for a binary search.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Thomas A. Russ
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <ymimzcre7pb.fsf@sevak.isi.edu>
Frank Buss <··@frank-buss.de> writes:
> Emre Sevinc wrote:
>
> > What if you were trying to write a binary search? You'd
> > have a platform that didn't indroduce such a bug but
> > what kind of a performance would it have (with a 1 billion
> > element array)? What would you value and why? Correctness
> > and being bug-free or having potential bugs but not
> > worry and think, "that's an extreme case and my typical
> > application stuff never goes to those extremes anyway."?
>
> As you wrote, in CL this is not a problem, because the index is automaticly
> adjusted to bignums, if it doesn't fit anymore in a fixnum. So if you are
> lucky and your CL implemenations provides an array-dimension-limit > 1e9,
> there should be no problem. Speed is not critical, because for 1e9 elements
> you need at most 30 steps for a binary search.
Well, there are implications in the above which will make the Google
example fail, and which may not be immediately obvious to less
experienced lisp users.
The limitation in Common Lisp is not in the computation of the index,
because (as you know) integer arithmetic doesn't overflow, but rather
rolls over into bignums.
The fault, though, lies in the array size limits that Common Lisp has.
Array indices are mandated by the CL standard to be fixnums. See for
example the specification of the value of ARRAY-TOTAL-SIZE-LIMIT, which
indicates that the value must be a FIXNUM. (This is alluded to in
Frank's reply, but I wanted to make it explicit).
So, if you happen to have a Lisp with fixnums that don't support one
billion you are out of luck. This would actually be quite common for
32-bit lisp implementations, since they often only have 28 or 29 bits
available for fixnum magnitude, so they would top out at 500 million or
less.
--
Thomas A. Russ, USC/Information Sciences Institute
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Maybe some of you have already heard about that BinarySearch bug:
>
> Extra, Extra - Read All About It: Nearly All Binary Searches
> and Mergesorts are Broken:
>
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
>
> When I've talked about that in public techno forum 2 groups of
> reactions formed:
>
> - Java programmers' reactions were something like, "come on,
> we're talking about a bug that reveals itself in a binary search
> operation that takes roughly 1 billion elements! Is that your
> typical daily array size? It may be for a Google programmer, but...
> So either roll your own binary search function, use IBM's or BEA's
> JVM, or wait it to be fixed for Mustang (or backported).
>
> - People who did some CL, Scheme, Python etc. reacted: Why
> try to solve a problem instead of using a language that didn't
> introduce the problem at all?
> [...]
> So my question's audience are people who had both CL and Java
> experience:
>
> What if you were trying to write a binary search? You'd
> have a platform that didn't indroduce such a bug but
> what kind of a performance would it have (with a 1 billion
> element array)? What would you value and why? Correctness
> and being bug-free or having potential bugs but not
> worry and think, "that's an extreme case and my typical
> application stuff never goes to those extremes anyway."?
>
I wrote a binary search in exactly two programming languages:
- first in Modula-2, where the type of the indexes is unsigned:
curmin: CARD32;
curmax: CARD32;
BEGIN
curmin:=min;
curmax:=max+1;
num:=(curmin+curmax)DIV 2;
therefore it can handle arrays of more than 2 giga entries. To have
more than 2 giga _different_ entries, you need much more than the
4GB maximum adressable space of these 32-bit machines, so it WILL NEVER
occur that a 2-gigaentry array is passed to this function.
Moreover, the Modula-2 language specifies that overflow errors are detected:
http://www.modula2.org/reference/operators.php
(And if you're foolish enough to run with overflow checking off, you
get the low order bytes of the results, which since it's still of
cardinal type is still positive and could still converge, IF you
could significantly pass an array of more than 2 giga entries
anyways).
The second is Common Lisp, where there is no problem of overflow with
integer, as long as you don't give array sizes much much bigger than
the Universe. So there WILL NEVER happen in this Universe.
In any cases, the algorithm is correct. It's the programs that are
written in C or in Java that are wrong, because the algorith says to
add to mathematical integer numbers, using the normal integer and
addition, and people try to implement it using modulo arithmetic of C
or Java.
The title of that article would have been more correct if labelled this way:
Extra, Extra - Read All About It: Nearly All C and Java Programs are Broken
> The reaction was simple: "So go and try to write your binary
> search in CL that does operations on an array having at least
> 1 billion elements."
Common Lisp arrays are specified to have a maximum size that can be as
low as 1024. So indeed, try to write a binary search on arrays having
at least 1 billion elements! You would have to build a high level
array abstraction, ARRAYs of ARRAYs of ARRAYs. More over, in 32-bit
implementations you're lucky if you can use more than 512 MB of the
RAM. So your high level array abstraction will have to store the
elements in a disk file.
Once you've done that, then you can come and implement the
1-billion-element binary search, without any sort of problem in CL.
--
__Pascal Bourguignon__ http://www.informatimago.com/
THIS IS A 100% MATTER PRODUCT: In the unlikely event that this
merchandise should contact antimatter in any form, a catastrophic
explosion will result.
Pascal Bourguignon wrote:
> More over, in 32-bit
> implementations you're lucky if you can use more than 512 MB of the
> RAM. So your high level array abstraction will have to store the
> elements in a disk file.
(make-array 500000000 :element-type '(unsigned-byte 1)) fails on most 32
bit Lisp implementations, but it would fit into 63 MB memory.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> wrote:
+---------------
| (make-array 500000000 :element-type '(unsigned-byte 1)) fails on most 32
| bit Lisp implementations, but it would fit into 63 MB memory.
+---------------
Works fine on CMUCL:
> (type-of (make-array 500000000 :element-type '(unsigned-byte 1)))
(SIMPLE-BIT-VECTOR 500000000)
>
Fails for 536870911 and above, though... ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kent M Pitman
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <ubqt5v75h.fsf@nhplace.com>
····@rpw3.org (Rob Warnock) writes:
> Frank Buss <··@frank-buss.de> wrote:
> +---------------
> | (make-array 500000000 :element-type '(unsigned-byte 1)) fails on most 32
> | bit Lisp implementations, but it would fit into 63 MB memory.
> +---------------
>
> Works fine on CMUCL:
>
> > (type-of (make-array 500000000 :element-type '(unsigned-byte 1)))
>
> (SIMPLE-BIT-VECTOR 500000000)
> >
>
> Fails for 536870911 and above, though... ;-}
Being myself a curious soul, I'm moved to ask: what are the values of
(type-of 500000000)
array-dimension-limit
most-positive-fixnum
in that implementation?
One reason that there's often a limit is that although you could store
that much, there's a desire by many implementors to use fixnums to do
the indexing, and if some of the bits of a 32 bit word have been given
up for tagging and whatnot (maybe sign bits, maybe other bits used for
GC or cdr-coding or some other thing), that can place an implicit
limit on the maximum array bound such that it's pointless to allow
someone to allocate an array so large that the indexing operations on
it won't work. Unless I've done my math wrong, 63MB = 63000000 8-bit
bytes, or 504000000 bits, which if you want to address each by an
index, then if MOST-POSITIVE-FIXNUM isn't at least that number, you're
going to lose. (Of course, ARRAY-DIMENSION-LIMIT is the authority on
how big you can make things, but it tends to be driven by the harder
limit imposed by MOST-POSITIVE-FIXNUM.)
e.g., in LispWorks 4.4.5 on my PC here at home:
CL-USER 1 > (type-of 500000000)
BIGNUM
CL-USER 2 > array-dimension-limit
8388607
CL-USER 3 > most-positive-fixnum
8388607
Kent M Pitman <······@nhplace.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Works fine on CMUCL:
| > (type-of (make-array 500000000 :element-type '(unsigned-byte 1)))
| > ==> (SIMPLE-BIT-VECTOR 500000000)
| > Fails for 536870911 and above, though... ;-}
|
| Being myself a curious soul, I'm moved to ask: what are the values of
| (type-of 500000000) array-dimension-limit most-positive-fixnum
| in that implementation?
+---------------
Why, FIXNUM[1], 536870911, and 536870911, of course!!
That's why I added the smiley face in the quoted posting.
I guess the humor was a little too subtle, sorry.
+---------------
| e.g., in LispWorks 4.4.5 on my PC here at home:
| CL-USER 3 > most-positive-fixnum
| 8388607
+---------------
Wow! Only 24-bit (signed) fixnums. That seems awfully small!
-Rob
[1] Well, actually CMUCL says:
> (type-of 500000000)
(INTEGER 500000000 500000000)
>
But what really matters is that:
> (fixnump 500000000)
T
>
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Thomas A. Russ
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <ymiac8odh0w.fsf@sevak.isi.edu>
····@rpw3.org (Rob Warnock) writes:
> Kent M Pitman <······@nhplace.com> wrote:
> +---------------
> | e.g., in LispWorks 4.4.5 on my PC here at home:
> | CL-USER 3 > most-positive-fixnum
> | 8388607
> +---------------
>
> Wow! Only 24-bit (signed) fixnums. That seems awfully small!
I noticed that in LispWorks/Windows as well.
LispWorks on Unix/Mac OS X has bigger 29?-bit fixnums.
I wonder if that is an effect of the processor architecture. Is there
something about x86 processors that make it much less desireable to mask
off something smaller than an entire 8-bit byte?
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ <···@sevak.isi.edu> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Wow! Only 24-bit (signed) fixnums. That seems awfully small!
|
| I noticed that in LispWorks/Windows as well.
| LispWorks on Unix/Mac OS X has bigger 29?-bit fixnums.
|
| I wonder if that is an effect of the processor architecture. Is there
| something about x86 processors that make it much less desireable to mask
| off something smaller than an entire 8-bit byte?
+---------------
I don't think so, since CMUCL & SBCL have 30-bit (signed) fixnums[1]
on 32-bit x86 platforms.
-Rob
[1] Trivia: There are technically *3* LowTag bits in a CMUCL "lispobj",
which would ordinarily restrict fixnums to 29 bits, but fixnums
take up both the #b000 and #b100 codepoints (for even & odd
fixnums, resp.), which gives them a 30-bit range after all.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Thomas A. Russ
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <ymir71zblae.fsf@sevak.isi.edu>
····@rpw3.org (Rob Warnock) writes:
> [1] Trivia: There are technically *3* LowTag bits in a CMUCL "lispobj",
> which would ordinarily restrict fixnums to 29 bits, but fixnums
> take up both the #b000 and #b100 codepoints (for even & odd
> fixnums, resp.), which gives them a 30-bit range after all.
So does that mean EVENP and ODDP are implemented as type tests? ;)
I suppose it is a clever way to get 7 type codes while still having 30
bit integers. Better than the naive solution of using 2 type bits and
only getting 4 codes.
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ <···@sevak.isi.edu> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > [1] Trivia: ... [In CMUCL] fixnums take up both the #b000 and #b100
| > codepoints (for even & odd fixnums, resp.)...
|
| So does that mean EVENP and ODDP are implemented as type tests? ;)
+---------------
Hardly! From "cmucl/src/compiler/srctran.lisp":
(def-source-transform evenp (x) `(zerop (logand ,x 1)))
(def-source-transform oddp (x) `(not (zerop (logand ,x 1))))
where DEF-SOURCE-TRANSFORM is heavy internal compiler macrology... ;-} ;-}
From there on it depends on the compiler to optimize the generic
LOGAND+test if it can, which it can if you declare the arg fixnum:
> (disassemble
(compile
(defun foo (x)
(declare (fixnum x))
(if (evenp x)
123
456))))
...[chatter]...
58946B78: .ENTRY FOO(x) ; (FUNCTION (FIXNUM) (OR # #))
...
...[generic arg-counting type-checking entry code]...
...
42: MOV EAX, EBX ; No-arg-parsing entry point
44: AND EAX, 4 ; See? It knows which bit to test
47: TEST EAX, EAX
49: JEQ L1
4B: MOV EDX, 1824 ; fixnum encoding for 456
50: L0: MOV ECX, [EBP-8] ; code for doing a return
53: MOV EAX, [EBP-4]
56: ADD ECX, 2
59: MOV ESP, EBP
5B: MOV EBP, EAX
5D: JMP ECX
5F: L1: MOV EDX, 492 ; fixnum encoding for 123
64: JMP L0
...
If you replace EVENP with ODDP the code is identical except that
the values of the "MOV EDX,nnn" immediate constants get swapped.
[In terms of branch prediction, I suppose you could say the compiler
is always predicting that fixnum arguments are even.]
+---------------
| I suppose it is a clever way to get 7 type codes while still having 30
| bit integers. Better than the naive solution of using 2 type bits and
| only getting 4 codes.
+---------------
I've seen other Lisps/Schemes in which fixnums use N-1 or N-2 bits,
pointers use N-2 or N-3 bits, and immediates chew up a byte or so
of type, leaving N-8 bits or some irregular sizes for the value.
In their docs you'll see complex type-decoding patterns like this,
from SCM's "code.doc":
IMMEDIATE: B,D,E,F=data bit, C=flag code, P=pointer address bit
................................
pointer PPPPPPPPPPPPPPPPPPPPPPPPPPPPP000
inum BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB10
ichr BBBBBBBBBBBBBBBBBBBBBBBB11110100
iflag CCCCCCC101110100
isym CCCCCCC001110100
IMCAR: only in car of evaluated code, cdr has cell's GC bit
ispcsym 000CCCC00CCCC100
iloc 0DDDDDDDDDDDDDDDEFFFFFFF11111100
gloc PPPPPPPPPPPPPPPPPPPPPPPPPPPPP001
CMUCL's encoding is fairly tame by comparison. From "internal-design.txt"
[out-of-date, so I've updated it to reflect a change to codepoint #b110
which let them go above 32 heap object types, since heap header words were
originally tagged as "other-immediate"s (now "other-immediate-{0,1}")]:
The following is a key of the three bit low-tagging scheme:
000 even fixnum
001 function pointer
010 other-immediate-0 (header-words, etc.)
011 list pointer
100 odd fixnum
101 structure pointer
110 other-immediate-1 (chars, symbol-value trap value, etc.)
111 other-pointer to data-blocks (other than conses, structures,
and functions)
So if the lispobj it's odd, it's a pointer; evens are fixnums and immediates.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Thomas A. Russ wrote:
> I wonder if that is an effect of the processor architecture. Is there
> something about x86 processors that make it much less desireable to mask
> off something smaller than an entire 8-bit byte?
And then there is x86-64...
[······@isis ~]$ uname -a
Linux isis.internal.dwavesys.com 2.6.16-1.2122_FC5 #1 SMP Sun May 21
15:01:10 EDT 2006 x86_64 x86_64 x86_64 GNU/Linux
[······@isis ~]$ sbcl
This is SBCL 0.9.12, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
* most-positive-fixnum
1152921504606846975
* ARRAY-TOTAL-SIZE-LIMIT
1152921504606846975
* (log most-positive-fixnum 2)
60.0
······@gmail.com <······@gmail.com> wrote:
+---------------
| And then there is x86-64...
...
| This is SBCL 0.9.12, an implementation of ANSI Common Lisp.
...
| 1152921504606846975
| * (log most-positive-fixnum 2)
| 60.0
+---------------
I suspect this was done for the same reason that 32-bit CMUCL
reports (log most-positive-fixnum 2) ==> 29, so that a fixnum "1"
is an underlying machine integer whose value is the length of a
"lispobj", i.e., 4 for 32 bits and 8 for 64 bits. That permits
array elements to be indexed by a fixnum by simply adding the
fixnum (maybe with a one or two element offset) to the address
of the array, as "cmucl/src/docs/internals/internal-design.txt"
says:
Effectively, there is one tag for immediate integers, two zeros.
This buys one more bit for fixnums, and now when these numbers
index into simple-vectors or offset into memory, they point to
word boundaries on 32-bit, byte-addressable machines. That is,
no shifting need occur to use the number directly as an offset.
This format has another advantage on byte-addressable machines
when fixnums are offsets into vector-like data-blocks, including
structures. Even though we previously mentioned data-blocks are
dual-word aligned, most indexing and slot accessing is word
aligned, and so are fixnums with effectively two tag bits.
Preserving this useful characteristic on a 64-bit machine means
using a "three zero bits" lowtag for fixnums there, which is what
SBCL appears to have done.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock <····@rpw3.org> wrote:
[... Python's tagging scheme ... ]
> Preserving this useful characteristic on a 64-bit machine means
> using a "three zero bits" lowtag for fixnums there, which is what
> SBCL appears to have done.
Yes, that's one reason 64-bit SBCL has a different lowtag size. On the
other hand, the unfinished CMUCL x86-64 port uses two zeroes lowtag
for fixnums, just like the x86 CMUCL. I don't know why that decision
was made.
--
Juho Snellman
From: Kent M Pitman
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <uu06tvcef.fsf@nhplace.com>
Juho Snellman <······@iki.fi> writes:
> Rob Warnock <····@rpw3.org> wrote:
> [... Python's tagging scheme ... ]
> > Preserving this useful characteristic on a 64-bit machine means
> > using a "three zero bits" lowtag for fixnums there, which is what
> > SBCL appears to have done.
>
> Yes, that's one reason 64-bit SBCL has a different lowtag size. On the
> other hand, the unfinished CMUCL x86-64 port uses two zeroes lowtag
> for fixnums, just like the x86 CMUCL. I don't know why that decision
> was made.
I didn't program in that system, so I don't know about the particulars of
the word size, but I'll bet that it's a byte-addressed machine and that
if there are two zeros, it means you're looking at counting going
00000 0
00100 8
01000 16
01100 24
10000 32
...etc.
That is, successive fixnums interpreted raw are pointers to every 8 bytes.
Your Q size (that is, the size of a Lisp pointer) is probably 4 bytes,
in which case 8 bytes is 2Q's, or the size of a cons. Or else your Q size
is 8 bytes, and this is the size of an array cell. But my point is that
there are various things that Lisp counts, and one of them is only very
rarely a "byte". Lisp is a non-byte-addressed language living often on
a byte-addressed machine. So I'm told it's handy to have things set up
so that integers can be used directly as a machine byte pointer without
further adjustment.
I think there's also some trick wherein the bits are chosen so that while
you have to shift and/or mask to multiply, you can do addition without
shifting (and maybe without masking) when you use this trick.
Bottom line: The cost of per-pointer type tagging can be noticeable in ways
other than just the space takes up--i.e., because of the runtime overhead--
if you don't have at least a few places where you can avoid fully
decoding things.
(I have this only second-hand because the only time I programmed
regularly in assembly language, this wasn't needed; the PDP10 was
designed by DEC as what amounted to an early Lisp Machine, with 18-bit
pointers and a 36-bit word and native instructions for half-word
access, and we didn't use tag bits--we used whole pages all of the
same type, so the pointer had type info implicit in the address. You
may laugh at 18-bit pointers, which were indeed painful, but 36-bit
integers were a much more comfortable size, at least.)
From: Kent M Pitman
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <u3bedj6al.fsf@nhplace.com>
Kent M Pitman <······@nhplace.com> writes:
> Juho Snellman <······@iki.fi> writes:
> ...
> > Yes, that's one reason 64-bit SBCL has a different lowtag size. On the
> > other hand, the unfinished CMUCL x86-64 port uses two zeroes lowtag
> > for fixnums, just like the x86 CMUCL. I don't know why that decision
> > was made.
>
> I didn't program in that system, so I don't know about the particulars of
> the word size, but I'll bet that it's a byte-addressed machine and that
> if there are two zeros, it means you're looking at counting going
> 00000 0
> 00100 8
> 01000 16
> 01100 24
> 10000 32
> ...etc.
> That is, successive fixnums interpreted raw are pointers to every 8 bytes.
> Your Q size (that is, the size of a Lisp pointer) is probably 4 bytes,
> in which case 8 bytes is 2Q's, or the size of a cons. Or else your Q size
> is 8 bytes, and this is the size of an array cell. But my point is that
> there are various things that Lisp counts, and one of them is only very
> rarely a "byte".
Gee, either no one is reading my posts or this newsgroup has gotten a lot
more polite/mellow while I've been away. It was late at night as I sent
this quoted text above and I was apparently not processing binary very well.
I realized a few minutes later as I was drifting off to sleep what the
error was, but I didn't doubt that some diligent soul would offer a
correction for the record before morning. No such luck.
Since no one did, and since I don't want some newbie to happen on this
and think I'm saying that (= #b100 8), I'll mention the inequality myself.
I always know it's a bad idea to actually _think_ when I'm tired.
It's much easier to _program_ and let the compute do the thinking.
I should have written:
(dotimes (i 5) (let ((j (ash i 2))) (format t "~&~5,'0B ~2D~%" j j)))
00000 0
00100 4
01000 8
01100 12
10000 16
Fortunately the rest of my remarks about the decision criteria stilll appear
coherent. I couldn't figure out why it would be counting by 2 Q's anyway,
so this simplifies the issue of what they were counting... If it's 1 Q,
it's presumably offering optimized array indexing.
Kent M Pitman <······@nhplace.com> wrote:
> Fortunately the rest of my remarks about the decision criteria stilll appear
> coherent. I couldn't figure out why it would be counting by 2 Q's anyway,
> so this simplifies the issue of what they were counting... If it's 1 Q,
> it's presumably offering optimized array indexing.
The point was that the lispobj size on the implementation/architecture
under discussion is 8 bytes (sorry, I thought this was obvious from
the context, but should've pointed it out explicitly). So using your
terminology the counting is done by 1/2 Q.
Now, this isn't a disaster on x86-64 since there's an indirect scaled
indexed addressing mode, so array indexing can still be done without
explicit shifting.
--
Juho Snellman
Juho Snellman <······@iki.fi> wrote:
+---------------
| Rob Warnock <····@rpw3.org> wrote:
| [... Python's tagging scheme ... ]
| > Preserving this useful characteristic on a 64-bit machine means
| > using a "three zero bits" lowtag for fixnums there, which is what
| > SBCL appears to have done.
|
| Yes, that's one reason 64-bit SBCL has a different lowtag size. On the
| other hand, the unfinished CMUCL x86-64 port uses two zeroes lowtag
| for fixnums, just like the x86 CMUCL. I don't know why that decision
| was made.
+---------------
I'm not sure it *was* explicitly made. I suspect that (non)decision
might need to be revisited [to do it the SBCL way] before the CMUCL
x86-64 port gets finished, since the "fixnums index lispobjs" is so
heavily wired into CMUCL...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Maybe some of you have already heard about that BinarySearch bug:
>
> Extra, Extra - Read All About It: Nearly All Binary Searches
> and Mergesorts are Broken:
>
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
>
> When I've talked about that in public techno forum 2 groups of
> reactions formed:
>
> - Java programmers' reactions were something like, "come on,
> we're talking about a bug that reveals itself in a binary search
> operation that takes roughly 1 billion elements! Is that your
> typical daily array size? It may be for a Google programmer, but...
> So either roll your own binary search function, use IBM's or BEA's
> JVM, or wait it to be fixed for Mustang (or backported).
>
> - People who did some CL, Scheme, Python etc. reacted: Why
> try to solve a problem instead of using a language that didn't
> introduce the problem at all?
>
> The reaction was simple: "So go and try to write your binary
> search in CL that does operations on an array having at least
> 1 billion elements."
>
> So my question's audience are people who had both CL and Java
> experience:
>
> What if you were trying to write a binary search? You'd
> have a platform that didn't indroduce such a bug but
> what kind of a performance would it have (with a 1 billion
> element array)? What would you value and why? Correctness
> and being bug-free or having potential bugs but not
> worry and think, "that's an extreme case and my typical
> application stuff never goes to those extremes anyway."?
>
I'd always go for correctness over performance. If performance is the
issue, then I'd suspect a binary search is the wrong algorithm.
My problem with allowing a 'bug' for performance is that by
definition, you don't fully understand what is occuring, otherwise you
would be able to avoid it. So, if you don't fully understand the
cause, then you cannot be certain exactly when the bug has an impact.
It would be, in some situations, acceptable to advise a library
routine or algorithm should only be used in specific circumstances -
such as stating you can only use the binary search for elements less
than N etc, but personally, I'd be wary of any library which had such
restrictions unless the specific reason for the restriction was well
documented and it could be guaranteed the bug would not surface at any
other time (but of course, whats a guarantee really worth?). you would
also have to guarantee the situation would never arrive and thats a
lot harder than it may seem. I've been burnt by such assumptions in
the past - written a bit of code which was supposed to only survive
until the next release or only deal with data sets that were a certain
size only to find that the code never gets replaced or the data sets
end up being much larger than anyone had predicted.
In a perfect world, correctness everytime. In a real world, sometimes
expediency means corners are cut, but I don't like it and only put up
with it because it is necessary in the larger picture.
Tim
--
tcross (at) rapttech dot com dot au
Emre Sevinc wrote:
> So my question's audience are people who had both CL and Java
> experience:
>
> What if you were trying to write a binary search? You'd
> have a platform that didn't indroduce such a bug but
> what kind of a performance would it have (with a 1 billion
> element array)? What would you value and why? Correctness
> and being bug-free or having potential bugs but not
> worry and think, "that's an extreme case and my typical
> application stuff never goes to those extremes anyway."?
Maybe the author of that article should've also mentioned the equally
authoritative book from Gray/Reuters, _Transaction Processing_, where
they mentioned their simple add(Uint, Uint) function which even had a
couple bugs in its first version. (For example, it advertised itself as
adding numbers, when it was really adding modulo the machine's word
size.)
Programmers typically want to make high-quality software. But the
economic context in which software is produced pressures many into
cutting corners. Common Lisp itself is a cut corner, a compromise
design, so the question is how many cut corners we accept.
I actually transliterated a binary search from Bentley's pseudocode
from _Programming Pearls_ into Java. I often mentally flagged + as
fake+, and may (or may not) have realized how it would've failed after
a certain point. But when you go so far as to accept Java for
application programming, you also accept a great raft of cut corners
and reality distortion fields.
Tayssir
--
Q: Which religion cites "The Invisible Hand" most often?
From: Thomas A. Russ
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <ymi64jcdgb9.fsf@sevak.isi.edu>
"Tayssir John Gabbour" <···········@yahoo.com> writes:
> Maybe the author of that article should've also mentioned the equally
> authoritative book from Gray/Reuters, _Transaction Processing_, where
> they mentioned their simple add(Uint, Uint) function which even had a
> couple bugs in its first version. (For example, it advertised itself as
> adding numbers, when it was really adding modulo the machine's word
> size.)
In thinking about this whole issue, I wondered if there would be some
benefit to code quality of choosing more precise names for arithmetic
types in programming languages. For example, instead of using the
somewhat misleading name "int" (which evokes the thought of integers),
perhaps they should instead be called "mod32int" or "intMod32" instead.
The idea being that the modular property of the type and its associated
arithmetic should be made explicit. That would then free up the name
"integer" or perhaps even "int" to represent bignums.
If one wanted or needed speed, one could use the modular variety, but at
least one would have to explicitly choose it. It is also somewhat
desirable to make the safer choice the more natural one to naively
choose.
That, and the use of a "decimal" type in addition to the binary floating
point numbers would, IMHO, go a long way to increasing the robustness of
software systems.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Bulent Murtezaoglu
Subject: Re: Buggy BinarySearch implementation, real life and a curious soul...
Date:
Message-ID: <87k67ts4v2.fsf@p4.internal>
>>>>> "TJG" == Tayssir John Gabbour <···········@yahoo.com> writes:
[...]
TJG> I actually transliterated a binary search from Bentley's
TJG> pseudocode from _Programming Pearls_ into Java. I often
TJG> mentally flagged + as fake+, and may (or may not) have
TJG> realized how it would've failed after a certain point. [...]
It should be (and perhaps was when I wasn't paying attention?) pointed
out that Bentley himself mentions word overflow in an exercise. I quote
from p41 of the 2nd. ed:
"As laborious as our proof of binary search was, it is still unfinished
by some standards. How would you prove that the program is free of
run-time errors (such as division by zero, word overflow, variables out
of declared range, [...]"
cheers,
BM