[Mono-list] Making a ruby.net compiler

[Jaroslaw Kowalski]

Hi!

Some thoughts about using lowest bits of a pointer to store some flags about
object type. I'm not sure if this is valid for this case (I'm not very good
in functional languages)

1. It makes your pointers unaligned, which I believe to be MUCH worse,
because it involves heavy penalty cycles in most current CPUs and is even
disallowed on some RISCs

2. If you want to align your pointers before each dereference - you can do
it but you have to add some additional instructions to the JIT output, which
would reduce the benefit of using bit flags

3. It also (may or may not) make your memory allocator be sub-optimal
because you have to deal with an internal fragmentation (you either allocate
contiguous block and discard the beginning of it or allocate contiguous one
and mangle the pointer, but you have to make a decision which takes time)

I wonder if you could have separate heaps (perhaps starting at some
well-known virtual memory addresses, like

0x40000000 - 0x7fffffff - heap for normal objects
0x80000000 - 0x8fffffff - heap for A objects
0x90000000 - 0x9fffffff - heap for B objects

This has an interesting property of being able to make decisions by checking
some pointer bits, keeps your pointers aligned and may even allow for the
jump table approach.

Just an idea.

Jarek

----- Original Message -----
From: "Michal Moskal" <malekith@pld-linux.org>
To: "Miguel de Icaza" <miguel@ximian.com>
Cc: "Fergus Henderson" <fjh@cs.mu.OZ.AU>; "Erik B?gfors" <erik@bagfors.nu>;
"sho tamashii" <sh0ii@yahoo.com>; "Mono List" <mono-list@ximian.com>
Sent: Sunday, May 11, 2003 7:37 PM
Subject: Re: [Mono-list] Making a ruby.net compiler


> [snip]
>
> Few more thoughts.
>
> 1. why should we optimize (special-case) the particular get_type call?
>
> Because it's *very* important in any language that has some kinds of
> variant (discriminating union) data structure, which would be compiled
> to subclasses. For example list is defined in ML:
>
> type 'a list = Cons of 'a * 'a list | Nil
>
> Which would be compiled to following Generic C#:
>
> class list<A> {}
> sealed class Cons<A> : list<A> {
>   A field_1;
>   list<A> field_2;
> }
> sealed class Nil<A> : list<A> {}
>
> And functions like (warning: this isn't optimal version :-)
>
> ML:
>
> let length = function
>     Cons (x, xs) -> 1 + length (xs)
>   | Nil -> 0
>
> C#:
>
> int length<A>(list<A> x)
> {
>   if (x is Cons<A>) { // (*)
>     return 1 + length(((Cons<A>)x).field_2);
>   } else {
>     return 0;
>   }
> }
>
> Here another issue should be raised, wrt Generic C#. It should be
> possible to write something like "if (x is Cons) {" at (*), because
> there is no need to check if type parameter A is the same.
>
> But this is just a comment.
>
> 2. bit patterns Fergus Henderson was talking about could be used to use
>    jump table in pattern matching. For example:
>
> type t =
>     Case1 of int
>   | Case2 of ...
>   | Case3 ...
>   ....
>   | Case23
>
> and then you have function:
>
> let f = function
>     Case1 (i) -> ...
>   | Case2 (...) -> ...
>   ...
>   | Case23 -> ...
>
> you would need to have 23 successive equality tests. It would be better
> to use jump table, but I'm not quite sure if it's at all possible in
> CIL. Anyway it can be done by having compiler-generated "int get_tag()"
> method in each of CaseN classes.
>
> Anyway this jump-table stuff doesn't present that-big performance hit
> as calling runtime function for each typeof.
>
> 3. if you are familiar with ILX, you should remember .classunion type
>    there, that just did discriminating unions.
>
> But I believe it isn't very good idea to put it in Mono, since it's
> very limited (namely it seems to fit OCaml variants, but not SML
> variants (things after of can have names), or OCaml polymorphic
> variants (one polymorphic variant can be in several types)).
>
> --
> : Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
> : PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h
>
> _______________________________________________
> Mono-list maillist  -  Mono-list@lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-list
>