RE: [Caml-list] Bug? Printf, %X and negative numbers

RE: [Caml-list] Bug? Printf, %X and negative numbers

[Gregory Morrisett]

>For generic code, it obviously requires either boxing or specialized 
>versions of the code, as I suggested in a different message.

The TIL (and TILT) and MLTON compilers support untagged integers.
As you suggest (and Xavier well knows) the hard part is dealing
with polymorphic code of which there is a lot in ML.  Consider, for
instance, a function such as map -- whether it produces integer
cons-cells depends upon how map is instantiated.  Life gets
complicated when you don't have tags.  TIL/T solved this by 
passing type representations to polymorphic functions.  These
representations could be used to construct header words for
objects to indicate which fields were[n't] pointers.  The information
was also used to support unboxed doubles, and a few other things.
See my thesis for more information.  

While this approach is viable, it has a lot of costs.  For
some of the tradeoffs, I suggest reading Xavier's excellent 
paper in the 1998 Types in Compilation workshop.  

MLTON avoids these issues by specializing polymorphic code at
all of its uses so that it becomes monomorphic (not unlike C++), 
at the price of separate compilation.

Generics in C# go yet another route with runtime specialization
which has distinct advantages like the possibility of supporting
polymorphic recursion (see Andrew Kennedy & co's papers.)    
There are different tradeoffs here, due to features such as
reflection and "instanceof", etc.

In short, there's a wealth of literature on this subject.  
Ocaml has taken a very expedient approach and in my opinion,
it would be difficult to produce an alternative that 
achieves the same performance without introducing a lot
of complexity.  

-Greg

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> While this approach is viable, it has a lot of costs.  For
> some of the tradeoffs, I suggest reading Xavier's excellent
> paper in the 1998 Types in Compilation workshop.

Do you mean the '97 paper (unboxing of floats in OCaml, among other 
things)?  I had read that one.  I just read the '98 paper, too, but it 
doesn't go into much detail.

> MLTON avoids these issues by specializing polymorphic code at
> all of its uses so that it becomes monomorphic (not unlike C++),
> at the price of separate compilation.

This is what I was suggesting.  With its whole-program analysis, this 
is obviously more straightforward for MLton, but I think it's also 
feasible for more practical compilers (without ending up with C++-like 
compile times).

I was thinking about keeping separate compilation by either using 
specialization as an optimization when the number of variations is 
reasonable at the point where the polymorphic code is implemented, or 
passing the generic code in a semi-compiled form and letting it be 
specialized on (first) use.  The latter is obviously better, but 
requires quite a bit of work on the intermediate compiled form and 
linking.

> Generics in C# go yet another route with runtime specialization
> which has distinct advantages like the possibility of supporting
> polymorphic recursion (see Andrew Kennedy & co's papers.)
> There are different tradeoffs here, due to features such as
> reflection and "instanceof", etc.

Thanks for the pointer.

> In short, there's a wealth of literature on this subject.
> Ocaml has taken a very expedient approach and in my opinion,
> it would be difficult to produce an alternative that
> achieves the same performance without introducing a lot
> of complexity.

I agree that the OCaml runtime makes good compromises that work well in 
practice.  Any added complexity would probably hurt symbolic code, 
which seems to have had a high priority in considerations of tradeoffs.

I don't feel strongly about the need for naked integers, so on my part 
this is just speculation and general curiosity.

What I would like is specialization of functors.  I hate using data 
structures that lose to Java in performance. ;-)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Lauri Alanko]

> I don't feel strongly about the need for naked integers, so on my part 
> this is just speculation and general curiosity.

For occasional hotspots where naked integers are essential for
performance, wouldn't the easiest solution be to use the equivalent of
GHC's unboxed ints: a special _non-polymorphic_ datatype that doesn't
have tags. This type would be given a kind different from other types to
prevent it from being used as a type parameter. Of course the GC still
needs to be prevented from following such values, but a separate stack
for them ought to do the trick.


Lauri Alanko
la@iki.fi

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> For occasional hotspots where naked integers are essential for
> performance, wouldn't the easiest solution be to use the equivalent of
> GHC's unboxed ints: a special _non-polymorphic_ datatype that doesn't
> have tags. This type would be given a kind different from other types 
> to
> prevent it from being used as a type parameter. Of course the GC still
> needs to be prevented from following such values, but a separate stack
> for them ought to do the trick.

Untagged non-pointers on the stack are already identified by frame 
descriptors.

Something like that but less restrictive could probably be implemented 
as optimized calling conventions for int32/int64 when explicitly 
specified.

Native-sized integers are currently handled unboxed locally inside 
functions, they just require boxing when stored in a block, passed as 
parameters or returned.  Using them is pretty inconvenient, though.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Brian Hurt]

Sorry for being quiet for a couple of days- came down with the flu.  I'm 
catching up on my email, so pardon the jumping into the middle of 
discussions.

On Thu, 3 Apr 2003, Ville-Pertti Keinonen wrote:
> 
> This is what I was suggesting.  With its whole-program analysis, this 
> is obviously more straightforward for MLton, but I think it's also 
> feasible for more practical compilers (without ending up with C++-like 
> compile times).
> 

I hadn't thought about polymorphism when I made my example.  And thinking 
about it, while it still might be doable, it becomes way more ugly.

One of the things I dislike about C++ template is code bloat.  This is the 
undiscussed cost of templates.  So you make a template foo<type>.  You 
create a foo<int> and the compiler has to spit out a specialized instance 
of foo to deal with ints.  Do foo<long> and now you have two foos.  Then 
you do foo<char>, foo<short>, foo<float>, foo<double>, foo<struct this>, 
foo<struct that>, etc.  And this is assuming that the compiler is smart 
enough to notice that foo<unsigned long> and foo<size_t> can generally use 
the same specialization.  And it takes heroic efforts to figure out that 
foo<int> and foo<unsigned int> might be able to use the same 
specialization.  Maybe.

So now you a dozen different specializations of foo<>.  All almost 
identical.  Say bye bye to any code locality.  And this isn't even 
mentioning badly designed templates, like the one I found (no kidding!) 
for an array template that took it's length as a parameter.  The compiler 
had to produce different specializations of the code for arrays length 3 
and arrays length 4.  Or some early C++ compilers which didn't have a way 
to say "this specialization is produced somewhere else", so if you used 
foo<int> in 100 different files, you got 100 copies of the specialization 
of foo onto ints.

This experience has made me violently opposed to specialization of code if 
it can be at all avoided.  I'll take the performance hit to avoid having 
uppity zillion almost-identical copies of my code kicking around.\

And this applies to Ocaml even more so.  I mean, consider the function:

let f x = ...

OK, so to specialize it for unboxed ints vr.s pointers takes two 
implementations of the function, f_pointer and f_int, right?  So now 
consider the function:

let f x y z w = ...

Do we need 16 different specializations for this function?  

No.  I'll take 31-bit ints any day.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> One of the things I dislike about C++ template is code bloat.  This is 
> the
> undiscussed cost of templates.  So you make a template foo<type>.  You

   ...

Specializations aren't the only reason C++ templates cause significant 
code growth.  Another is that they (in the case of the most commonly 
used HP/SGI STL, at least) use inlining very heavily, so each 
instantiation is big and a lot of inlined code is instantiated several 
times all over the place.

For some cases, inlined handling of data structures is good.  Consider 
the performance of the STL sort vs. anything based on a callback or 
virtual method.

I'm not a big fan of C++ templates, but I don't think they're a very 
good argument against all specialization.

> And this applies to Ocaml even more so.  I mean, consider the function:

Less so, I would think, since most types are compatible.

> let f x = ...
>
> OK, so to specialize it for unboxed ints vr.s pointers takes two
> implementations of the function, f_pointer and f_int, right?  So now
> consider the function:
>
> let f x y z w = ...
>
> Do we need 16 different specializations for this function?

Not if they're generated at the point where they are first used(*), in 
which case a maximum of 16 specializations are created - compared to 
C++, where there is no maximum, and you often end up having things like 
std::map<std::string, my_object *> and std::map<std::string, 
my_other_object *> which are in fact identical.

(*) Obviously this requires some adjustments to the compilation model.

A quick grepping through .mli files in the OCaml source distribution 
reveals that there are zero instances of the string 'd but quite a few 
instances of 'c, which would seem to indicate that four variables is 
not common.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Falk Hueffner]

Brian Hurt <brian.hurt@qlogic.com> writes:

> So now you a dozen different specializations of foo<>.  All almost
> identical.  Say bye bye to any code locality.  And this isn't even
> mentioning badly designed templates, like the one I found (no
> kidding!)  for an array template that took it's length as a
> parameter.  The compiler had to produce different specializations of
> the code for arrays length 3 and arrays length 4.

You didn't choose a very good example. The compiler will certainly
inline both operator[] and .size(), which will result in probably
smaller and certainly faster code.

-- 
	Falk

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] Bug? Printf, %X and negative numbers

[brogoff]

On Wed, 2 Apr 2003, Gregory Morrisett wrote:
> MLTON avoids these issues by specializing polymorphic code at
> all of its uses so that it becomes monomorphic (not unlike C++), 
> at the price of separate compilation.

And, as I think you're implying, polymorphic recursion. 

In Okasaki's PFDS book, he describes the techniques you'd use to convert 
non-uniform types to uniform ones and rewriting the functions. Has anyone 
played with the idea of automating these transformations, so that a MLTON like 
monomorphizing compiler could work for a language with non uniform recursion? 

No, I'm not suggesting that for OCaml. I agree that the OCaml implementation is 
at some sweet spot where it isn't too complex, is very efficient, compiles 
quickly, etc. 

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] Bug? Printf, %X and negative numbers

[Fabrice Le Fessant]

 
> I agree that the OCaml runtime makes good compromises that 
> work well in practice.  Any added complexity would probably 
> hurt symbolic code, which seems to have had a high priority 
> in considerations of tradeoffs.

Just my two pence: in MLdonkey, int64 are used everywhere instead of
int, and instead of int32, which are two
small for file sizes. So, it will not benefit from any optimization on
int32. However, it would benefit 
from a new type 'long', that would be at-least a 63-bit integer.
Depending on the platform, this type could 
be implemented either by a traditionnal int (with the integer-bit set,
on 64-bit platforms), or by an int64 
on other platforms.

Since in the next years, more and more computers will be 64-bit, and
more and more applications will need 
support for integers in the range 33-bit ... 63-bit, this could be more
interesting than optimizing 32-bit 
integers (using the 'long' type, a program that would have used 32-bit
integers, would have the guaranty 
that the longs are not allocated on 64-bit platforms). Moreover, it can
probably be implemented in the 
Pervasives module without any changes in the compiler. But maybe int32
are already implemented by a normal int 
on 64-bit platforms ?


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Bug? Printf, %X and negative numbers

[Brian Hurt]

$ ocaml
        Objective Caml version 3.06

# Printf.printf "%08X\n" (1 lsl 30);;
C0000000
- : unit = () 
# Printf.printf "%010X\n" (1 lsl 30);;
00C0000000
- : unit = ()
# 

I expected output of 40000000, not C0000000.  Note that this isn't a case 
of simple sign extension, as the second example demonstrates.  Where'd the 
extra bit come from?

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Yutaka OIWA]

>> On Fri, 28 Mar 2003 15:19:16 -0600 (CST), Brian Hurt <brian.hurt@qlogic.com> said:

Brian> $ ocaml
Brian>         Objective Caml version 3.06

Brian> # Printf.printf "%08X\n" (1 lsl 30);;
Brian> C0000000
Brian> - : unit = () 
Brian> # Printf.printf "%010X\n" (1 lsl 30);;
Brian> 00C0000000
Brian> - : unit = ()
Brian> # 

Brian> I expected output of 40000000, not C0000000.  Note that this isn't a case 
Brian> of simple sign extension, as the second example demonstrates.  Where'd the 
Brian> extra bit come from?

Brian> Brian

The extra bit comes from sign extension: (1 lsl 30) is the minimal
negative Caml integer.  The cause exists in byterun/ints.c:
31bit-value 0x40000000 is sign-extended to 32bit C-integer 0xc0000000
by macro Long_val, then sprintf in the C library puts extra "00" in
front of it (equivalent to zero-extension).
Maybe the unsigned version of Long_val is needed.

# 1 lsl 30 - 1;;
- : int = 1073741823
# Printf.sprintf "%u" (1 lsl 30);;
- : string = "3221225472"

-- 
Yutaka Oiwa              Yonezawa Lab., Dept. of Computer Science,
      Graduate School of Information Sci. & Tech., Univ. of Tokyo.
      <oiwa@yl.is.s.u-tokyo.ac.jp>, <yutaka@oiwa.shibuya.tokyo.jp>
PGP fingerprint = C9 8D 5C B8 86 ED D8 07  EA 59 34 D8 F4 65 53 61

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Xavier Leroy]

> $ ocaml
>         Objective Caml version 3.06
> 
> # Printf.printf "%08X\n" (1 lsl 30);;
> C0000000
> 
> I expected output of 40000000, not C0000000.  Note that this isn't a case 
> of simple sign extension, as the second example demonstrates.  Where'd the 
> extra bit come from?

As Yutaka Oiwa said, it comes from the conversion from Caml 31-bit
integers to C 32-bit integers, which performs sign extension.

Even though 0x40000000 and 0xC0000000 denote the same Caml int, I
agree this behavior is very surprising and should be fixed.  I'll look
into this.  Thanks for reporting the issue.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Brian Hurt]

On Sun, 30 Mar 2003, Xavier Leroy wrote:

> As Yutaka Oiwa said, it comes from the conversion from Caml 31-bit
> integers to C 32-bit integers, which performs sign extension.
> 
> Even though 0x40000000 and 0xC0000000 denote the same Caml int, I
> agree this behavior is very surprising and should be fixed.  I'll look
> into this.  Thanks for reporting the issue.


Having looked at it a bit myself, the fix will probable be *ahem* 
interesting.  Effectively, you have to stop using C's printf.  Either 
that, or parse the format string a second (third?) time to see wether you 
need to do a signed or unsigned int conversion.  Or, I suppose, we could 
completely redesign Ocaml to use 32-bit ints and do something else to 
differentiate ints from pointers :-).

More pragmatically, I think this behavior should just be documented.  
"Broken as designed".  Once you know about it, it's annoying not critical.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> need to do a signed or unsigned int conversion.  Or, I suppose, we 
> could
> completely redesign Ocaml to use 32-bit ints and do something else to
> differentiate ints from pointers :-).

That would only require a redesign of part of the runtime.  As far as I 
can tell, at least for native code, it should only affect the 
representation of mixed data, garbage collection and use in polymorphic 
functions, none of which would necessarily be that bad for performance 
if designed and optimized properly.

On the other hand, the efficiency of the current implementation 
probably has a lot to do with good choices of compromises in allocating 
the bits of block headers...

I wonder how much work it would be to test how efficiently such a 
change could be done without going all the way...has anyone looked into 
this?

> More pragmatically, I think this behavior should just be documented.
> "Broken as designed".  Once you know about it, it's annoying not 
> critical.

And maybe %u should be disabled altogether if it can never produce any 
correct results that differ from %d.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Xavier Leroy]

> Having looked at it a bit myself, the fix will probable be *ahem* 
> interesting.  Effectively, you have to stop using C's printf.  Either 
> that, or parse the format string a second (third?) time to see wether you 
> need to do a signed or unsigned int conversion.

It's no big deal, really.  (See the working sources on camlcvs.inria.fr.)
The formats are already parsed three(!) times:
  - once in Caml (module Printf)
  - once in C to determine the size of the buffer to hold the result
        (file byterun/ints.c)
  - once in the printf() C library function itself.
The way I fixed it, the signed/unsigned distinction is done in the
second parsing, although it could also be done during the first.

> Or, I suppose, we could 
> completely redesign Ocaml to use 32-bit ints and do something else to 
> differentiate ints from pointers :-).

If you can find a "something else" that is faster than systematically
boxing the 32-bit ints, you'll be hailed as the savior in compiler
circles :-)

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[David Brown]

On Tue, Apr 01, 2003 at 10:19:46AM +0200, Xavier Leroy wrote:

> > Or, I suppose, we could 
> > completely redesign Ocaml to use 32-bit ints and do something else to 
> > differentiate ints from pointers :-).
> 
> If you can find a "something else" that is faster than systematically
> boxing the 32-bit ints, you'll be hailed as the savior in compiler
> circles :-)

Easy, just convince everyone to start using 33 bit computers.

Dave

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Tim Freeman]

Somebody I don't know said:
> Or, I suppose, we could 
> completely redesign Ocaml to use 32-bit ints and do something else to 
> differentiate ints from pointers :-).

Then Xavier said:
>If you can find a "something else" that is faster than systematically
>boxing the 32-bit ints, you'll be hailed as the savior in compiler
>circles :-)

I'm guessing that the standard solution to doing full-word ints with a
garbage collector is to generate some code for each data structure
that plugs into the garbage collector and knows what fields are ints
and what fields are pointers.  That's the way the gcc compiler did it
as of 3.0.1 or so.  (In that case the code was manually generated.)

I don't know if this would be faster than OCAML's approach.  You'd pay
for more code in your cache, and for an indirect goto for each block
that is garbage collected (unless you managed to garbage collect them
in batches of blocks of identical type, or you organized things so in
the absence of polymorphism it was a subroutine call instead of an
indirect goto.  You could maybe even inline the subroutine call
sometimes.  Hmm.).  You'd benefit because you don't have to do the bit
twiddling that's done for every arithmetic operation now, and because
it should be faster to decide not to follow the non-pointers during
garbage collection.  Straight-line code is often faster than branching
for modern architectures.

Surely this has been discussed before, although perhaps not on this
mailing list.  Can someone point to a paper that analyzes the various
tradeoffs?

-- 
Tim Freeman                                                  tim@fungible.com
Which is worse: ignorance or apathy? Who knows? Who cares?
GPG public key fingerprint ECDF 46F8 3B80 BB9E 575D  7180 76DF FE00 34B1 5C78 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Brian Hurt]

On Tue, 1 Apr 2003, Tim Freeman wrote:

> Somebody I don't know said:
> > Or, I suppose, we could 
> > completely redesign Ocaml to use 32-bit ints and do something else to 
> > differentiate ints from pointers :-).
> 
> Then Xavier said:
> >If you can find a "something else" that is faster than systematically
> >boxing the 32-bit ints, you'll be hailed as the savior in compiler
> >circles :-)
> 
> I'm guessing that the standard solution to doing full-word ints with a
> garbage collector is to generate some code for each data structure
> that plugs into the garbage collector and knows what fields are ints
> and what fields are pointers.  That's the way the gcc compiler did it
> as of 3.0.1 or so.  (In that case the code was manually generated.)

I thought they were using Boehm's GC?  Which is conservative, in that if 
it looks like a pointer, it treats it as a pointer.  Note that this means 
that you can't do copying, as you don't dare change the pointers (they 
might be).  This also means that a small percentage of garbage is falsely 
retained because of bogus pointers (although in practice not enough to 
worry about- Boehm has some papers on real world applications).

This is more than good enough for C/C++, but Ocaml puts rather more stress 
on it's GC.  Especially as I remember seeing statistics that your average 
ML program allocates a word of memory every six instructions- an insane 
amount of allocation for a C program.

I was thinking of just a bitmask.  You are always allocating into the
minor heap.  You just define the low 1/32nd of the minor heap a bitmask of
what is a pointer and what isn't.  This would probably slow down
allocation- not by much, would be my prediction, but it would slow down
allocation.  You may gain some of that cost back by not needing to do the
shifts and ors we currently do to deal with the low bit.  I can't predict
what the overall performance delta would be- not even if it will be
positive or negative.

However, I would predict that it will be small enough, even if positive,
to make it not worth the effort.  

For my bitarray code I'd like unboxed 32-bit ints.  Primarily because it'd
allow me to turn my current divides and modulos into shifts and ands.  Or 
rather, have the compiler do it for me.  There is a performance difference 
x/31 and x/32.

But a bigger problem than that, probably (I haven't actually done any 
timing, so I can't say for certain) is repetive divides.  I have a lot of 
code like:
    let bits_per_word = Sys.wordsize - 1;

    let dosomething idx =
        let wordidx = idx / bits_per_word
        and bitidx = idx mod bits_per_word
        in
        ...

The code that 3.06 produces for the above uses the idiv instruction twice-
once for the quotient, once for the remainder.  A little optimization 
would have it issued only once, and use both operands.  I played a little 
bit with writting a ldiv function, which let me play with the C interface, 
but produced enough other inefficiencies to make it not worth the effort.  
Ah well.  Minor nit.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> I was thinking of just a bitmask.  You are always allocating into the
> minor heap.  You just define the low 1/32nd of the minor heap a 
> bitmask of
> what is a pointer and what isn't.  This would probably slow down
> allocation- not by much, would be my prediction, but it would slow down
> allocation.  You may gain some of that cost back by not needing to do 
> the
> shifts and ors we currently do to deal with the low bit.  I can't 
> predict
> what the overall performance delta would be- not even if it will be
> positive or negative.

I suspect that would be quite slow, since you have to do one bit 
operation for each word of each allocation (optimizing them is 
difficult because you don't know the alignment).

One way of doing this much faster is just having a the first word of 
any mixed block (homogenous blocks aren't a problem) indicate the 
number of pointers and always put the pointers first.

Of course wasting an entire word on this is nasty when less bits would 
do...but the bits of the current block header are pretty tightly 
allocated.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Tim Freeman]

From: Ville-Pertti Keinonen <will@exomi.com>
>One way of doing this much faster is just having a the first word of 
>any mixed block (homogenous blocks aren't a problem) indicate the 
>number of pointers and always put the pointers first.
>
>Of course wasting an entire word on this is nasty when less bits would 
>do...but the bits of the current block header are pretty tightly 
>allocated.

Most blocks are small, so one could make a scheme that fits the number
of pointers into the current block header for small blocks and uses an
extra word for larger blocks.  This would have the desirable side
effect of increasing the limit on the size of arrays.  Code that
accesses inside a block often knows the size of the block it's
accessing, so you can often precompute whether that extra word is
there and avoid taking a branch to decide whether to skip it.

-- 
Tim Freeman                                                  tim@fungible.com
Which is worse: ignorance or apathy? Who knows? Who cares?
GPG public key fingerprint ECDF 46F8 3B80 BB9E 575D  7180 76DF FE00 34B1 5C78 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> Most blocks are small, so one could make a scheme that fits the number
> of pointers into the current block header for small blocks and uses an
> extra word for larger blocks.  This would have the desirable side
> effect of increasing the limit on the size of arrays.  Code that
> accesses inside a block often knows the size of the block it's
> accessing, so you can often precompute whether that extra word is
> there and avoid taking a branch to decide whether to skip it.

Code that accesses fields of a block always knows the size unless it's 
an array (or string), in which case bounds checking also needs to be 
done, but it couldn't contain mixed data anyhow.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Brian Hurt]

On Tue, 1 Apr 2003, Ville-Pertti Keinonen wrote:

> 
> > I was thinking of just a bitmask.  You are always allocating into the
> > minor heap.  You just define the low 1/32nd of the minor heap a 
> > bitmask of
> > what is a pointer and what isn't.  This would probably slow down
> > allocation- not by much, would be my prediction, but it would slow down
> > allocation.  You may gain some of that cost back by not needing to do 
> > the
> > shifts and ors we currently do to deal with the low bit.  I can't 
> > predict
> > what the overall performance delta would be- not even if it will be
> > positive or negative.
> 
> I suspect that would be quite slow, since you have to do one bit 
> operation for each word of each allocation (optimizing them is 
> difficult because you don't know the alignment).

For structures 32 words or less, you can do it like (using x86 assembly 
language here):
	movl	heap_top, %eax
	movl	%eax, %ecx
	andl	$31, %ecx
	movl	%eax, %ebx
	shrw	$5, %bx	; /* partial register stall- oh well */
	movl	$bit_pattern, %esi
	xorl	%edi, %edi
	shldl	%cl, %esi, %edi
	shll	%cl, %esi
	orl	%esi, (%ebx)
	orl	%edi, 4(%ebx)

10 instructions, no branchs, only one partial register stall (which can
probably be removed at the cost of four more instructions), only one
'complex' instruction (the shld) which might take more than a clock cycle.  
Some rearrangement could probably give us 2, maybe 3 instructions issued
per clock.  We're probably looking at single digit clock cycles here.  
Note that I'm assuming the minor heap is 64K (removing the partial stall 
would also solve this).

On the other side of this equation, we have the overhead of dealing with 
the low bit being set.  This does have a performance cost.  How much of 
one depends upon what you're doing with the ints.  But we're not talking 
about more than an instruction or two per access.  With few accesses per 
allocation it's probably a loss- with more access per allocation, it's 
probably a win.  But either way, we're talking about single digit clock 
cycles.

By way of comparison, on the P4 a branch mispredict costs 20-28 clock 
cycles, a cache miss costs 100-300 clock cycles, and a page fault millions 
of clock cycles.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

> For structures 32 words or less, you can do it like (using x86 assembly
> language here):

   ...actual code snipped...

Ok, that's not necessarily too bad.

I guess I was just intuitively dismissing anything that felt like it 
had more than a couple of instructions of "overhead".   I'm probably 
also biased by SMP-thinking - read-modify-write operations feel 
inherently evil. ;-)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Brian Hurt]

On Tue, 1 Apr 2003, Ville-Pertti Keinonen wrote:

> 
> > For structures 32 words or less, you can do it like (using x86 assembly
> > language here):
> 
>    ...actual code snipped...
> 
> Ok, that's not necessarily too bad.
> 
> I guess I was just intuitively dismissing anything that felt like it 
> had more than a couple of instructions of "overhead".   I'm probably 
> also biased by SMP-thinking - read-modify-write operations feel 
> inherently evil. ;-)
> 

For SMP you want different minor heaps for every thread.  Adding the lock 
prefix to an instruction costs ~100 clock cycles.  Much better to simply 
give each thread it's own minor heap.  64K isn't that much memory.  And 
there are stunts you can pull if you threads spend most of their life 
blocked to decrease the number of minor heaps you need.

Note that you implicitly have a read-modify-write cycle already in your
allocation.  You need to read the top-of-heap pointer, save off the
original pointer, increment by the size you are allocating, and write the 
incremented pointer back, all automatically.  A wonderful application of 
load locked/store conditional, if only we had it in the x86.  Without it, 
you basically need to grab a spinlock before updating.  Thus the lock 
prefix.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Andreas Rossberg]

Ville-Pertti Keinonen wrote:
> 
> One way of doing this much faster is just having a the first word of any 
> mixed block (homogenous blocks aren't a problem) indicate the number of 
> pointers and always put the pointers first.

I'm afraid such a scheme is incompatible with polymorphism, where a slot 
may or may not be a pointer, depending on the actual instantiation. 
Still, polymorphic code must be able to operate uniformingly in both 
cases, i.e. the slot may not be shuffled around.

   - Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
  as kids, we would all be running around in darkened rooms, munching
  magic pills, and listening to repetitive electronic music."
  - Kristian Wilson, Nintendo Inc.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

On Wednesday, Apr 2, 2003, at 11:55 Europe/Helsinki, Andreas Rossberg 
wrote:

> I'm afraid such a scheme is incompatible with polymorphism, where a 
> slot may or may not be a pointer, depending on the actual 
> instantiation. Still, polymorphic code must be able to operate 
> uniformingly in both cases, i.e. the slot may not be shuffled around.

For generic code, it obviously requires either boxing or specialized 
versions of the code, as I suggested in a different message.

I don't particularly like the pointer-count/shuffling idea, it was just 
an example of something that would require far fewer instructions to 
initialize compared to the bitmap.

The main difference between the approaches I've been thinking of and 
what Brian Hurt has been suggesting is that he's thinking of 
externalizing the tag bit while I'm thinking about taking a basically 
boxed approach and optimizing away boxing in as many cases as possible.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Ville-Pertti Keinonen]

>> Or, I suppose, we could
>> completely redesign Ocaml to use 32-bit ints and do something else to
>> differentiate ints from pointers :-).
>
> If you can find a "something else" that is faster than systematically
> boxing the 32-bit ints, you'll be hailed as the savior in compiler
> circles :-)

I'm probably missing something because I don't see how this should be 
*that* difficult.  There are language implementations that use 
untagged, at-least-sometimes-unboxed native integers and have garbage 
collection, and I don't believe they perform horribly.

Representation of mixed data and stack frames can be done using various 
combinations of conservative garbage collection, layout descriptors and 
selective boxing.  This is a matter of choosing a set of compromises.  
Most such solutions would probably have slightly higher garbage 
collection and memory overhead than OCaml currently does, but I 
wouldn't expect all of the possible approaches to perform worse than 
boxing all integers (with the obvious exception of cases where integers 
are hardly used).

Generic code could be optimized by generating specialized versions of 
the code for the unboxed/untagged types in cases where the aren't more 
than, say, two or three unknown types.  Unused versions can be 
eliminated at link time.  This could also be done more efficiently and 
completely by changing the compilation model a bit more.

Even with the current tagged integers, specialized versions of generics 
would significantly increase performance in some cases.  Currently 
integer keys in polymorphic or functor maps are much slower than they 
need to be.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Bug? Printf, %X and negative numbers

[Claude Marche]

>>>>> "Brian" == Brian Hurt <brian.hurt@qlogic.com> writes:

    Brian> $ ocaml
    Brian>         Objective Caml version 3.06

    Brian> # Printf.printf "%08X\n" (1 lsl 30);;
    Brian> C0000000
    Brian> - : unit = () 
    Brian> # Printf.printf "%010X\n" (1 lsl 30);;
    Brian> 00C0000000
    Brian> - : unit = ()
    Brian> # 

    Brian> I expected output of 40000000, not C0000000.  Note that this isn't a case 
    Brian> of simple sign extension, as the second example demonstrates.  Where'd the 
    Brian> extra bit come from?

Sorry to come back at the very beginning of this thread, but I'd like
to add my two centeuros: I feel that the first answer is correct, but
the second is wrong. Why? (1 lsl 30) is -2^30, right ? and the format
"%nX" means the hexadecimal 2-complement representation of the
argument, on n hexdigits, right ? So I think

  Printf.printf "%08X\n" (1 lsl 30);;

should write C0000000 and

  Printf.printf "%010X\n" (1 lsl 30);;

should write FFC0000000.



-- 
| Claude Marché           | mailto:Claude.Marche@lri.fr |
| LRI - Bât. 490          | http://www.lri.fr/~marche/  |
| Université de Paris-Sud | phoneto: +33 1 69 15 64 85  |
| F-91405 ORSAY Cedex     | faxto: +33 1 69 15 65 86    |

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners