Discussion:
[fonc] Parameterized Word Tagging: Any interest?
Kurt Stephens
2008-07-29 01:59:46 UTC
Permalink
Is anybody interested in adding parameterized word tagging in libid, idc and
up through Jolt?

If this was implemented in higher-levels of abstraction we could introduce
different tagging schemes to support locatives, flonums, etc. This could lead
to more language features, reduced memory usage and garbage on smaller
hardware and better performance on 64-bit machines that don't need the lower 3
bits of the machine word for object addresses due to alignment.

Hardcoded 1-bit tags doesn't give much room for future ideas or any other
immediates. I could continue the work into libid, but I haven't looked much
at Jolt yet; I'm not sure where to start.

Preliminary results as applied to libid here:

http://kurtstephens.com/node/60

Kurt Stephens
John Leuner
2008-07-29 12:40:03 UTC
Permalink
Post by Kurt Stephens
If this was implemented in higher-levels of abstraction we could introduce
different tagging schemes to support locatives, flonums, etc. This could lead
to more language features, reduced memory usage and garbage on smaller
hardware and better performance on 64-bit machines that don't need the lower 3
bits of the machine word for object addresses due to alignment.
Hardcoded 1-bit tags doesn't give much room for future ideas or any other
immediates. I could continue the work into libid, but I haven't looked much
at Jolt yet; I'm not sure where to start.
http://kurtstephens.com/node/60
32-bit machines also don't need the lower 3 bits if you align all
objects by 8 bytes.

In my Church-State implementation I adopted some of the conventions used
by the SBCL lisp implementation, see the tags here

http://subvert-the-dominant-paradigm.net/repos/hgwebdir.cgi/bootstrap/file/3ec558141ebc/church/runtime/church_types.state

and the sbcl page describing the tags:

http://sbcl-internals.cliki.net/tag%20bit

The main rationale is that fixnums can be added without shifting (and
can be used to index word arrays without shifting).

In general I agree with Adrian Kuhn (who commented on your blog post)
that the benefits of one tagging scheme versus another are doubtful. In
the context of idc or my language implementation, there are many avenues
for optimization open for exploration which will likely yield more
benefit.

John
Kurt Stephens
2008-07-29 16:26:03 UTC
Permalink
Post by John Leuner
32-bit machines also don't need the lower 3 bits if you align all
objects by 8 bytes.
Obviously. In fact many common allocators will align to 8 bytes.
Post by John Leuner
In my Church-State implementation I adopted some of the conventions used
by the SBCL lisp implementation, see the tags here
http://subvert-the-dominant-paradigm.net/repos/hgwebdir.cgi/bootstrap/file/3ec558141ebc/church/runtime/church_types.state
http://sbcl-internals.cliki.net/tag%20bit
The main rationale is that fixnums can be added without shifting (and
can be used to index word arrays without shifting).
Currently, libid and idc only support 1 tag: fixnum or allocated object. All
fixnums in idc and above require masking and shifting before operations. A
fixnum operation heavy program, for example, would benefit from using 00 tags,
as in SBCL, unless tags can be optimized away by type inference or declaration.

The idea to parameterize the tagging, to avoid hard-wired low-level decisions
about tag schemes by opening it up to higher levels of abstraction, Jolt for
example. Hard-coded decisions about tagging and word size created problems
when porting it to 64 bits.
Post by John Leuner
In general I agree with Adrian Kuhn (who commented on your blog post)
that the benefits of one tagging scheme versus another are doubtful. In
the context of idc or my language implementation, there are many avenues
for optimization open for exploration which will likely yield more
benefit.
John
Adrian correctly pointed out that tagging is a time/space trade-off. I did
demonstrate that different processors did perform differently by varying
tagging schemes. There is an interest in porting FoNC to smaller and larger
architectures. If tagging schemes have limited benefit then why decide on any
tagging scheme? There are valid reasons modern systems do not use high-bit
tags; I propose there are valid reasons to not hard-code a particular tagging
scheme into a flexible system like FoNC.

Kurt
John Leuner
2008-07-30 20:39:12 UTC
Permalink
Post by Kurt Stephens
Currently, libid and idc only support 1 tag: fixnum or allocated object. All
fixnums in idc and above require masking and shifting before operations. A
fixnum operation heavy program, for example, would benefit from using 00 tags,
as in SBCL, unless tags can be optimized away by type inference or declaration.
The idea to parameterize the tagging, to avoid hard-wired low-level decisions
about tag schemes by opening it up to higher levels of abstraction, Jolt for
example. Hard-coded decisions about tagging and word size created problems
when porting it to 64 bits.
Yes, it will useful to have this before porting to new architectures.
Has anybody started on an (x86) 64-bit port of the code generator? I
would like to collaborate if someone is working on this.
Post by Kurt Stephens
Post by John Leuner
In general I agree with Adrian Kuhn (who commented on your blog post)
that the benefits of one tagging scheme versus another are doubtful. In
the context of idc or my language implementation, there are many avenues
for optimization open for exploration which will likely yield more
benefit.
John
Adrian correctly pointed out that tagging is a time/space trade-off. I did
demonstrate that different processors did perform differently by varying
tagging schemes.
Yes, the current tagging scheme (with 0 as nil) seemed to perform best
in your benchmark. But will it make a difference for more typical usage
(such as idc compiling itself)?
Post by Kurt Stephens
There is an interest in porting FoNC to smaller and larger
architectures. If tagging schemes have limited benefit then why decide on any
tagging scheme? There are valid reasons modern systems do not use high-bit
tags; I propose there are valid reasons to not hard-code a particular tagging
scheme into a flexible system like FoNC.
Sure

John
Dale Schumacher
2008-07-30 23:42:48 UTC
Permalink
Post by John Leuner
Post by Kurt Stephens
Adrian correctly pointed out that tagging is a time/space trade-off. I did
demonstrate that different processors did perform differently by varying
tagging schemes.
Yes, the current tagging scheme (with 0 as nil) seemed to perform best
in your benchmark. But will it make a difference for more typical usage
(such as idc compiling itself)?
Post by Kurt Stephens
There is an interest in porting FoNC to smaller and larger
architectures. If tagging schemes have limited benefit then why decide on any
tagging scheme? There are valid reasons modern systems do not use high-bit
tags; I propose there are valid reasons to not hard-code a particular tagging
scheme into a flexible system like FoNC.
I'm new to this list, so pardon me if this is off-topic.

I'm working on a prototype micro-kernel (in C) that currently runs on
x86 but is ultimately targeted to run on an ARM processor as well. On
the ARM, it is possible to include a shift into any data access opcode
without incurring additional execution cycles. This creates a
different set of interesting trade-offs WRT performant type tagging.

I've experimented with a couple of different tagging schemes, some
intended to leave bits available for marking by the garbage collector.
I've isolated all the tagging policies into a small set of macros.
This allowed me to switch from using 3-MSB to 2-LSB without changing
anything except the macro definitions.

The meta-question I have is: Is this an appropriate place to discuss
micro-kernel design issues in general, or is it VPRI/COLA specific?
It seems to me that we have a lot in common. I have certainly enjoyed
learning from your published experiences.
Martin McClure
2008-07-31 02:14:02 UTC
Permalink
Post by John Leuner
Has anybody started on an (x86) 64-bit port of the code generator? I
would like to collaborate if someone is working on this.
I'd identified that as my next fonc-related task, but haven't really
started on it, and may not get a chance to work on it in the next couple
of weeks. But if you do pick this up before I get a chance to, I'd like
to hear what you're doing.

Regards,

-Martin
Kjell Godo
2008-08-23 09:09:01 UTC
Permalink
Post by Martin McClure
Post by John Leuner
Has anybody started on an (x86) 64-bit port of the code generator? I
would like to collaborate if someone is working on this.
I'd identified that as my next fonc-related task, but haven't really
started on it, and may not get a chance to work on it in the next couple
of weeks. But if you do pick this up before I get a chance to, I'd like
to hear what you're doing.
Regards,
-Martin
Does COLA fonc run on Windows?
Derek Kuliński
2008-08-23 17:18:33 UTC
Permalink
Hello Kjell,
Post by Kjell Godo
Does COLA fonc run on Windows?
You should be able to compile it on cygwin (http://www.cygwin.com/).
--
Best regards,
Derek mailto:***@takeda.tk
CCNA, SCSA, SCNA, LPIC, MCP certified

-- Backup not found: (A)bort (R)etry (T)hrowup
Kjell Godo
2008-08-24 00:44:08 UTC
Permalink
Okay I want to compile it on cygwin.
Which version of fonc should I use?
What is Jolt? What is Coke? What is Pepsi? Cola is Lisp
plus Smalltalk right? Plus a lot of weird stuff like variables
that are macros and weird stuff like that.
Is there a debugger I can use to step through its execution?
Are there test cases?
I don't know C so which compiler should I use? gcc?
Could you point me to the mailing list where others have
tried to do this? Or perhaps I could be the example here?
Seems like most of the people here know gcc really really well.
I don't. I only know Smalltalk, Scheme, Prolog, although I did C in the
1980s.
I hated Microsoft's C compiler so much that I swore I would
never touch C again. But turbo C was good.
If you help me then my example might help others too.
I like to document. So this tendency might be useful to you.
Post by Derek Kuliński
Hello Kjell,
Post by Kjell Godo
Does COLA fonc run on Windows?
You should be able to compile it on cygwin (http://www.cygwin.com/).
--
Best regards,
CCNA, SCSA, SCNA, LPIC, MCP certified
-- Backup not found: (A)bort (R)etry (T)hrowup
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc
Derek Kuliński
2008-08-24 07:20:21 UTC
Permalink
Hello Kjell,

Saturday, August 23, 2008, 5:44:08 PM, you wrote:

First of all, I'm learning about all that myself, so my answers might
not be necessary correct (I hope someone will correct me if I'm
wrong).
Post by Kjell Godo
Okay I want to compile it on cygwin.
Which version of fonc should I use?
This one is a bit old, but is more likely to compile without problems:
http://piumarta.com/software/cola/idst-20070918.tar.gz

The latest version you can download using:
svn co http://piumarta.com/svn2/idst/trunk idst

you would need to install svn (either stand alone or through cygwin)
Post by Kjell Godo
What is Jolt?
It's a function language with a scheme-like syntax. It's a bit like
scripting language, since you don't compile it to an executable,
though it compiles to machine code at run time.
Post by Kjell Godo
What is Coke?
Here's what I'm confused, either it is a separate language, or it is
another name for jolt.

Though if it is a different language, then it's extremely similar to
jolt:
http://piumarta.com/software/cola/coke.html
(pretty much everything described here work in jolt)
Post by Kjell Godo
What is Pepsi?
Pepsi is object oriented prototype-based language, that resembles
Smalltalk. Unlike Jolt, it is compiled into an executable.
I think another name for it is also idst.

http://piumarta.com/software/cola/pepsi.html

Both of those links might not be completely up to date, but I think it
should provide most of needed information (especially if you already
know Scheme and Smalltalk)
Post by Kjell Godo
Cola is Lisp plus Smalltalk right?
Actually COLA is Pepsi & Coke/Jolt
Post by Kjell Godo
Plus a lot of weird stuff like variables
that are macros and weird stuff like that.
Is there a debugger I can use to step through its execution?
As far as I know - no. If there is I'm really interested.
Because those languages are late bound sometimes is very hard to debug
them. With Pepsi, when you compile something, it doesn't mean it will
run, and when the compiled program won't run it won't display you line
code (perhaps that might be somehow solved by storing this information
in executable?)
Post by Kjell Godo
Are there test cases?
For Pepsi, there's object/st80/test-st80.st though it is more
about testing the st80 library.
There are also many examples.
Post by Kjell Godo
I don't know C so which compiler should I use? gcc?
I think it will work best with gcc (it might not even work with other
compilers at all)
Post by Kjell Godo
Could you point me to the mailing list where others have
tried to do this? Or perhaps I could be the example here?
As far as I know this is the only mailing list for Cola.
As for example, if you install cygwin (compiling on linux might be
less likely to fail though) you should install gcc, make and other
dependencies, you can also install svn (subversion) when you're at it)

Then go to the directory that you extracted and type:
make

That will take a while.

Once you finish that, you don't have to install it, just go to one of
examples and type make run to see how it works.
Post by Kjell Godo
Seems like most of the people here know gcc really really well.
I don't. I only know Smalltalk, Scheme, Prolog
Good news for you:
Once you compile it (and if everything goes well, typing make should
do everything) you won't really have to worry about C. Most C related
stuff is only when you want to call libc functions from Pepsi or Jolt.

I'm a C guy, and I actually never learned Smalltalk and Scheme, so
learning about Jolt and Pepsi takes a lot of time for me. I think it
should be way easier for you.
Post by Kjell Godo
although I did C in the 1980s.
I don't think it changed that much since then ;)
Though I doubt you'll need it much (most of the .c files are generated
from the Pepsi source code)
Post by Kjell Godo
I hated Microsoft's C compiler so much that I swore I would
never touch C again. But turbo C was good.
If you help me then my example might help others too.
I like to document. So this tendency might be useful to you.
I don't think you should have problem with it, as long as you install
everything you need in cygwin.
If you'll still have problems I'll try my best to help.
--
Best regards,
Derek mailto:***@takeda.tk
CCNA, SCSA, SCNA, LPIC, MCP certified

It's not bogus, it's an IBM standard
Aaron Gray
2008-07-29 18:02:55 UTC
Permalink
Post by John Leuner
Post by Kurt Stephens
If this was implemented in higher-levels of abstraction we could introduce
different tagging schemes to support locatives, flonums, etc. This could lead
to more language features, reduced memory usage and garbage on smaller
hardware and better performance on 64-bit machines that don't need the lower 3
bits of the machine word for object addresses due to alignment.
Hardcoded 1-bit tags doesn't give much room for future ideas or any other
immediates. I could continue the work into libid, but I haven't looked much
at Jolt yet; I'm not sure where to start.
http://kurtstephens.com/node/60
32-bit machines also don't need the lower 3 bits if you align all
objects by 8 bytes.
Mozilla's SpiderMonkey Javascript implementation used in Firefox and other
Mozilla environments uses 3 bit tags as follows :-

000 - untagged reference to an Object
001 - a 31 bit int
010 - tagged reference to a Double
100 - tagged reference to a String
110 - tagged Boolean

There is more room within the boolean's space to have thurther encoded
types.

The only issues are extra "coing" and "uncoding" code, which could be
implicitly generated in generated code and speed issues.

If its usage could be virtual and transparent in generated code (ie there or
not there on a generation flag) and maybe also modifiable in instances then
we would have the best of all worlds.

Aaron
Michael FIG
2008-08-01 00:34:39 UTC
Permalink
Hi,

I agree that this would be an interesting feature. However, I think
it's not a good idea to try implementing until Pepsi uses Jolt as a
backend (i.e. Coke is bootstrapped). Then, the tagging operations can
be Jolt macros instead of (icky) CPP macros.

I'm still curious how far Ian is getting with jolt3... I'd be
interested in helping that effort along if he (hint, hint) would
publish what he's working on in SVN or else send an e-mail describing
what needs to be done (another hint). ;)
--
Michael FIG <***@fig.org> //\
http://michael.fig.org/ \//
Kjell Godo
2008-08-24 00:27:16 UTC
Permalink
Are Jolt macros Object Oriented?

In picoLARC most of the macros are Object Oriented and are called
by message passing in exactly the same way that all other message
passing is done. Programmers are just Objects that return
trees of syntax Objects which can then be compiled. Programmers
are called during the compile time of Classes.

picoLARC is multi language using dialects of Lisp for each language
so like there is a Prolog version of picoLARC inside of picoLARC
the expressions of which can be embedded anywhere in picoLARC.

So instead of doing [ smalltalk ... ( lisp ... ) ... ] picoLARC does it
( picoLARC ... ( prolog ... ) ... ) or ( prolog ... ( picoLARC ... ) ... )
which is more general because you can get more different languages
to participate. ( c# ... ( prolog ... ) ... )

So each dialect in picoLARC can make use of the OOP macro
system because they all are dialects of lisp( picoLARC ).

Hopefully there could be a C dialect of Lisp( picoLARC ). But I
can't imagine it yet. If you can imagine a C based dialect of
Lisp please show it to me. There would be no closures. And it
would be stack based rather than environment based I know that
much. But how close it could be to C I don't know.

I think that it would be good if Cola Jolt macros could be OOP.
Post by Michael FIG
Hi,
I agree that this would be an interesting feature. However, I think
it's not a good idea to try implementing until Pepsi uses Jolt as a
backend (i.e. Coke is bootstrapped). Then, the tagging operations can
be Jolt macros instead of (icky) CPP macros.
I'm still curious how far Ian is getting with jolt3... I'd be
interested in helping that effort along if he (hint, hint) would
publish what he's working on in SVN or else send an e-mail describing
what needs to be done (another hint). ;)
--
http://michael.fig.org/ \//
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc
Loading...