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
|