Re: [Ocaml-lib-devel] a bug in BitSet?

[Janne H. <ja...@hy...>]

Sorry about that previous broken mail.. Had a little accident with my mouse.

Nicolas Cannasse wrote:
> It's not so easy.
> Let's take a blit for example, you might not want to put assert before every
> blit call so you will write a blit stub that does asserts before directly
> calling blit, and I'm not sure ocamlopt can inline such method easily.
> We should not modify the source code of ExtLib for testing, since testing
> purpose is actually to detect wrong behavior. Having separate tests is ok
> for me, but if we need to add also tests inside extLib sources (assert) that
> make twice the same somehow. If there is some overflow problems we can
> detect them with appropriate testing (for example run a GC major after every
> call ).

I have to disagree here.

Tests are written to find bugs.  In order to make the tests more
useful, they should also be written such that they make it more easy
to actually fix the bugs.  Assertions have proven themselves in
practice to do just that: to make it more easy locate and fix bugs.
Debugging with asserts is easy, since you can isolate your bug into a
small region of code.  The same cannot be said about getting a random
segfault in a random function when executing some totally unrelated
code.

If properly used, assertions do not incur a performance cost.  As you
suggested, small wrapper functions go extremely well with assertions.
A compiler shouldn't have much of a problem inlining such wrapper
functions, since with -noassert (assertions turned off) these wrappers
will only contain a jump to the "wrappee" function.  (See more details
below)

I am not proposing big changes to the library.  What I'm suggesting is
that if we find a problematic piece of code (such as the current
BitSet in CVS), we could minefield a couple strategic points with
assertions and leave them there.  This would allow us to check that
there are no buffer overruns in the code.  These checks would only get
compiled in "debug build".  In all other occasions they would be
turned off and thus shouldn't cause any overhead.

I also think that any new code should be allowed to have assertions in
it.  This suggests that -noassert should be in the Makefile, at least
if you want these checks to be turned off.

***

Since earlier in my post I am claiming that assertions do not incur a
run-time cost, I made a test to provide some evidence that this is
indeed the case.

I have an example from BitSet.ml.  In BitSet, there exists the
following loop (which reads out-of-bounds):

--cut--
let intersect t t' =
     for i = 0 to t.len - 1 do
         bset t.data i ((bget t.data i) land (bget t'.data i))
     done
--cut--

The innerloop of the above when compiled with ocamlopt for x86:

--cut--
.L548:
     movl    %ecx, %edx
     sarl    $1, %edx
     movl    %edx, 0(%esp)
     movl    (%eax), %edi
     movl    %ecx, %esi
     sarl    $1, %esi
     movl    (%ebx), %edx
     movzbl  (%edx, %esi), %edx
     lea 1(%edx, %edx), %esi
     movl    %ecx, %ebp
     sarl    $1, %ebp
     movl    (%eax), %edx
     movzbl  (%edx, %ebp), %edx
     lea 1(%edx, %edx), %edx
     andl    %esi, %edx
     sarl    $1, %edx
     movl    0(%esp), %esi
     movb    %dl, (%edi, %esi)
     movl    %ecx, %esi
     addl    $2, %ecx
     movl    4(%esp), %edx
     cmpl    %edx, %esi
     jne .L548
--cut--

As expected, there are no bound checks.

The next step I did was to change bget and bget functions so that they
are actually wrappers for functions fast_get and fast_set.  I added
bounds check assertions to bget and bset.  The changes are detailed in
the patch below.

Naturally, if we compile with assertions on, the bget/bsets are not
inlined.  Instead, they get turned into function calls:

--cut--
.L588:
     movl    0(%esp), %eax
     movl    (%eax), %eax
     call    camlBitSet__bget_65
.L590:
     movl    %eax, 4(%esp)
     movl    8(%esp), %eax
     movl    (%eax), %eax
     movl    12(%esp), %ebx
     call    camlBitSet__bget_65
.L591:
     movl    %eax, %ecx
     movl    4(%esp), %ebx
     andl    %ebx, %ecx
     movl    8(%esp), %ebx
     movl    (%ebx), %eax
     movl    12(%esp), %ebx
     call    camlBitSet__bset_68
.L592:
     movl    12(%esp), %ebx
     movl    %ebx, %ecx
     addl    $2, %ebx
     movl    %ebx, 12(%esp)
     movl    16(%esp), %eax
     cmpl    %eax, %ecx
     jne .L588
--cut--

Again, this was expected.

Now, we turn off assertions by adding -noassert to ocamlopt command
line and compile the code with wrapped bget/bset.  We get the
optimized loop back:

--cut--
.L553:
     movl    (%eax), %edi
     movl    (%ebx), %edx
     movl    %esi, %ecx
     sarl    $1, %ecx
     movzbl  (%edx, %ecx), %ecx
     lea 1(%ecx, %ecx), %ecx
     movl    (%eax), %ebp
     movl    %esi, %edx
     sarl    $1, %edx
     movzbl  (%ebp, %edx), %edx
     lea 1(%edx, %edx), %edx
     andl    %ecx, %edx
     movl    %esi, %ecx
     sarl    $1, %ecx
     sarl    $1, %edx
     movb    %dl, (%edi, %ecx)
     movl    %esi, %edx
     addl    $2, %esi
     movl    0(%esp), %ecx
     cmpl    %ecx, %edx
     jne .L553
--cut--

You can do a little better than that by changing "intersect" function
by reading t/t'.data pointers into local variables outside of the
loop:

--cut--
let intersect t t' =
   let buf = t.data
   and buf' = t'.data in
   for i = 0 to t.len - 1 do
	bset buf i ((bget buf i) land (bget buf' i))
   done
--cut--

Which yields:

--cut--
.L553:
     movl    %ebx, %eax
     sarl    $1, %eax
     movzbl  (%edi, %eax), %eax
     lea 1(%eax, %eax), %eax
     movl    %ebx, %edx
     sarl    $1, %edx
     movzbl  (%esi, %edx), %edx
     lea 1(%edx, %edx), %edx
     andl    %eax, %edx
     movl    %ebx, %eax
     sarl    $1, %eax
     sarl    $1, %edx
     movb    %dl, (%esi, %eax)
     movl    %ebx, %eax
     addl    $2, %ebx
     cmpl    %ecx, %eax
     jne .L553
--cut--

Well it still isn't all that hot, but I guess it's been already
discussed and agreed that if you want more performance, you should use
a library written more specifically for your purpose.

Here are the assertion changes made to BitSet.ml:

<patch>
diff -u -r1.12 bitSet.ml
--- bitSet.ml   22 Dec 2004 07:59:46 -0000      1.12
+++ bitSet.ml   27 Dec 2004 14:42:26 -0000
@@ -21,11 +21,27 @@
  type intern

  let bcreate : int -> intern = Obj.magic String.create
-external bget : intern -> int -> int = "%string_unsafe_get"
-external bset : intern -> int -> int -> unit = "%string_unsafe_set"
+external fast_get : intern -> int -> int = "%string_unsafe_get"
+external fast_set : intern -> int -> int -> unit = "%string_unsafe_set"
  external fast_bool : int -> bool = "%identity"
-let bblit : intern -> int -> intern -> int -> int -> unit = Obj.magic 
String.blit
-let bfill : intern -> int -> int -> int -> unit = Obj.magic String.fill
+let fast_blit : intern -> int -> intern -> int -> int -> unit = 
Obj.magic String.blit
+let fast_fill : intern -> int -> int -> int -> unit = Obj.magic String.fill
+let fast_length : intern -> int= Obj.magic String.length
+
+let bget s ndx =
+  assert (ndx >= 0 && ndx < fast_length s);
+  fast_get s ndx
+
+let bset s ndx v =
+  assert (ndx >= 0 && ndx < fast_length s);
+  fast_set s ndx v
+
+let bblit src srcoff dst dstoff len =
+  fast_blit src srcoff dst dstoff len
+
+let bfill dst start len c =
+  fast_fill dst start len c
+
</patch>


Best regards,
Janne