Proof of functional optimization
Brandon J. Van Every
comp.compilers and starting to learn about compiler implementation to
answer it. Although certainly I trundle on with my own research, and I
have an instinct as to what the comp.lang.functional crowd would say
(which is why I don't bother to ask them), I might as well pop it as a
Scheme specific question.
Functional Programming makes many claims about how the world will be a
better place if only we follow the paradigm. My question is, do
compilers deliver this better world in practice? The main form of
'betterness' I'm interested in is performance. I'm interested in how
functional recombination can produce blisteringly fast code, given the
right compiler and the right problem domain. I get the feeling that
many FP adherants aren't so interested in this goal, however. They may
be more interested in type safety, proving correctness, metaprogramming,
or "sufficiently good" performance traded against other considerations.
It seems FP has a big tent for all the things it could promise. The
part of the tent I'm interested in is performance.
So, when you profile and optimize your Scheme code, do you see evidence
that your compiler is doing a good job? Assuming you stick to FP, do
you see piles of functions eliding out of existence?
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
20% of the world is real.
80% is gobbledygook we make up inside our own heads.
Jesper Louis Andersen
> Functional Programming makes many claims about how the world will be a
> better place if only we follow the paradigm.
I do not think we are claiming this. Rather, I would claim that if functional
programming were used more, programs would be more abstract, there would
be fewer lines of code and it would be easier to glue different pieces of
programming code together.
I would not claim that it is for the better. The optimist in me say it would,
but playing the devils advocate, we would have as many lousy library
specifications as we have now, as many too specialized or generalized
libraries etc.
> My question is, do compilers deliver this better world in practice?
> The main form of 'betterness' I'm interested in is performance.
It is disturbing you are so obsessed with performance, I would think.
> I'm interested in how functional recombination can produce
> blisteringly fast code, given the right compiler and the right
> problem domain. I get the feeling that many FP adherants aren't so
> interested in this goal, however. They may be more interested in
> type safety, proving correctness, metaprogramming, or "sufficiently
> good" performance traded against other considerations.
Performance is an issue. A language 8 times slower than typical C-code will
not be used for a number of applications, where the performance is crucial. If
you are 1.2 times slower, the added abstraction might help you to. For example,
enable you to spread out your workload better on your cluster. To squeeze the
last couple of percents of performance out from a CPU you need to target that
CPU specially, taking care of oddities, caches, special features,
Instruction Level Parallellism issues etc.. It is not feasible for most FP
projects to take this road, since the time is a constraint here. I do not think
they should either.
The key is interaction between languages. You could write the intensive
operations in C and then use them from scheme. You could also devise a
language for, say GPUs, and then use this new language to describe GPU
instructions in. I know this is the way I would go if I should write a game.
Also, writing the monstrous games we see today cannot be done by one man. What
I think is much more important in the game development industry is the ability
to manage a team. The actual language used is less important. In such a
setting, the perfect solution is not an option. You have to produce a game by,
say 5 years. So if someone has an almost working Rendering engine in C++, you
are going to use that instead of writing your own.
If you want to see Bigloo scheme, SML, Haskell or some other FP language
literally devastate C++ in a game context, you should start small. Pick one
part of a game and implement that part in Scheme. The rendering engine is
probably not the best choice as it usually works low-level. I'd go as
far as saying you need a Domain Specific Language for that.
> It seems FP has a big tent for all the things it could promise. The
> part of the tent I'm interested in is performance. So, when you
> profile and optimize your Scheme code, do you see evidence that your
> compiler is doing a good job?
It depends on what you mean by good job. The low-level scheduling optimizations
are lacking behind the C counterparts, because they take too much time to
invest in. On the other hand, some function inliners are much cleverer than
what I have seen in most C compilers.
--
jlouis
Brandon J. Van Every
>It depends on what you mean by good job. The low-level scheduling optimizations
>are lacking behind the C counterparts, because they take too much time to
>invest in. On the other hand, some function inliners are much cleverer than what I have seen in most C compilers.
>
>
What particular implementations have you observed the clever inlining?
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
When no one else sells courage, supply and demand take hold.
Förster vom Silberwald
> I do not think we are claiming this. Rather, I would claim that if
functional
> programming were used more, programs would be more abstract, there
would
> be fewer lines of code and it would be easier to glue different
pieces of
> programming code together.
The other day I have been reading an article which stated that C++ does
a lot of useless things and has a lot of really big overhead to perform
when analyzing code and making a programm. Or better said any C++
compiler.
They went on to say in that article, that the biggest problems with
user systems (e.g. Mac OSX, Windows) are not so much the design but the
impossibility to add useful stuff based on C++.
When reading the article I have been wondering whether all the tools
like CommonLisp, OCaml, Scheme, Haskell perform unnecessary tasks too.
I mean if you start off with Haskell, Clean, CommonLisp, etc. modules
and your system grows bigger. Does the latter mean adding new design
principles will be easier than under C++ regimes?
That reminds me on some crazy comments on comp.lang.forth. There are
really guys who claim that garbage collection is a big overhead and
they have everything under control by themself. They go on to say that
garbage collection is the axis of evil.
Schneewittchen
Sunnan
> That reminds me on some crazy comments on comp.lang.forth. There are
> really guys who claim that garbage collection is a big overhead and
> they have everything under control by themself. They go on to say that
> garbage collection is the axis of evil.
That's not crazy if you're using (and properly debugging) a stack based
language, like dc, forth or postscript.
I've programmed plenty of dc and it's usually fine. You can have memory
leaks if you aren't careful - these are detected by printing the stack
every now and then, during the development process.
Sunnan
> I've programmed plenty of dc and it's usually fine. You can have memory
> leaks if you aren't careful - these are detected by printing the stack
> every now and then, during the development process.
I'm often pondering making a stack-based, non-gc:d interpreter for a
very scheme-like language, to use for writing some tight parts of the
hypothetical scheme based operating system we're all dreaming about.
This would basically reverse the s-exps, putting the arguments on the
stack, popping off, and every now and then check the stack for leaks,
which would be manually fixed. It probably wouldn't work, I don't know.
Ray Dillinger
No, it (apparently) works fine. That's the basic sketch of how
the interpreter for "new lisp" works without a garbage collector.
There are certain things you won't be able to express, but you
can make a capable little language out of it.
Bear
Ulrich Hobelmann
> No, it (apparently) works fine. That's the basic sketch of how
> the interpreter for "new lisp" works without a garbage collector.
What is "new lisp". It's hard to google for that term ;)
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Ray Dillinger
> Ray Dillinger wrote:
>
>> No, it (apparently) works fine. That's the basic sketch of how
>> the interpreter for "new lisp" works without a garbage collector.
>
>
> What is "new lisp". It's hard to google for that term ;)
>
Warning; I haven't used the language much. I've just been
looking around the lispy-language design space and it's one
of the things I ran across.
Bear
Ulrich Hobelmann
>> What is "new lisp". It's hard to google for that term ;)
>>
>
> http://www.newlisp.org/
Thanks. That looks interesting...
Jesper Louis Andersen
> What particular implementations have you observed the clever inlining?
Take a search on ``polyvariance'' for instance.
--
jlouis
Marcin 'Qrczak' Kowalczyk
> http://www.newlisp.org/
>
> Warning; I haven't used the language much. I've just been
> looking around the lispy-language design space and it's one
> of the things I ran across.
For me it's a disaster.
Because of lack of GC there is no sharing of values: all values are
copied when passed as function arguments or put in data structures
(except for some builtin functions). There is no lexical scoping,
numbers are only fixnums and floats, there silly restrictions with the
only justification being interpreter simplicity (e.g. length of quoted
string constants is limited to 2048, strings cannot contain NULs),
ugly FFI which e.g. represents pointers as integers on the newLisp
side (doesn't work when a pointer doesn't fit in C int), pointless
rules like cons behaving like list when the second argument is not a
list (no practical and safe code would make use of this).
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Matthias Blume
I just had a brief look at their FAQ, and it seems worse than a
disaster. They don't even know what call-by-value means and claim
their "copy the whole tree" approach to parameter passing is
call-by-value (implicitly saying that, e.g., Scheme, is
call-by-reference).
Ulrich Hobelmann
> Because of lack of GC there is no sharing of values: all values are
sharing values is a (memory) efficiency hack ;)
At least it's an implementation thing that doesn't give you are
real features.
> copied when passed as function arguments or put in data structures
call-by-value is quite common...
> (except for some builtin functions). There is no lexical scoping,
ok, that sucks.
> numbers are only fixnums and floats, there silly restrictions with the
Like in most languages.
> only justification being interpreter simplicity (e.g. length of quoted
> string constants is limited to 2048, strings cannot contain NULs),
Ok, that's stupid again...
> ugly FFI which e.g. represents pointers as integers on the newLisp
> side (doesn't work when a pointer doesn't fit in C int), pointless
Any 32bit platform, no?
> rules like cons behaving like list when the second argument is not a
> list (no practical and safe code would make use of this).
Uuuuuh.
Matthias Blume
> Marcin 'Qrczak' Kowalczyk wrote:
>> Because of lack of GC there is no sharing of values: all values are
>
> sharing values is a (memory) efficiency hack ;)
False. In the presence of mutation, sharing is semantically significant.
> At least it's an implementation thing that doesn't give you are real
> features.
<gnoring mutable state for a moment>
Unless you consider being able to run the program on your
computer (as opposed to not being able to do that) a feature. Without
sharing, linear space requirements can turn into exponential space
requirements.
</gnoring mutable state for a moment>
>> copied when passed as function arguments or put in data structures
>
> call-by-value is quite common...
Quibble: This is not call-by-value. Scheme is call-by-value. Common
Lisp is call-by-value. C is call-by-value. None of these language
make deep copies of their arguments.
Marcin 'Qrczak' Kowalczyk
>> Because of lack of GC there is no sharing of values: all values are
>
> sharing values is a (memory) efficiency hack ;)
It's a significant efficiency hack. Without it a function which
descends into a list using 'rest' takes O(N^2) time because each
'rest' copies the rest of the list.
The only way to pass mutable objects around in Newlisp is to make
contexts. A context must be named with a symbol, and as far as I see
you must invent unique symbols yourself.
>> copied when passed as function arguments or put in data structures
>
> call-by-value is quite common...
I find call-by-value which copies an arbitrary number of subobjects
only in C++, which provides pointers to avoid copying.
>> ugly FFI which e.g. represents pointers as integers on the newLisp
>> side (doesn't work when a pointer doesn't fit in C int), pointless
>
> Any 32bit platform, no?
Yes, but what about 64bit platforms?
Code quality is poor. Symbol names are sometimes restricted to at most
255 characters (when reading from a stream), but sometimes not; why to
have such restriction at all? "Efficient red black tree" does strcmp
twice:
while (current != NIL_SYM)
{
if(strcmp(key, current->name) == 0) /* already exists */
return(current);
parent = current;
current = (strcmp(key, current->name) < 0) ?
current->left : current->right;
}
Newlisp has hardwired 32bit-ness in various places, e.g. in conversion
to integer:
else if(*(double *)&cell->aux > 2147483647.0) *number = 0x7FFFFFFF;
else if(*(double *)&cell->aux < -2147483648.0) *number = 0x80000000;
else *number = *(double *)&cell->aux;
This snippet shows that Newlisp rarely signals errors, it prefers to
return an incorrect answer, like Perl.
A nice portable way of storing a floating point value by overwriting
two adjacent integers with a double:
typedef struct
{
UINT type;
void * next;
UINT aux;
UINT contents;
} CELL;
CELL * stuffFloat(double * floatPtr)
{
CELL * cell;
cell = getCell(CELL_FLOAT);
*(double *)&cell->aux = *floatPtr;
return(cell);
Brandon J. Van Every
This leads me to many papers, but not (in an obvious timesaving way) to
implementations. Is there a specific implementation you had in mind
that "delivers the performance goods?"
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
On Usenet, if you're not an open source hippie who
likes to download and play with programming toys
all day long, there's something wrong with you.
Jesper Louis Andersen
>>Take a search on ``polyvariance'' for instance.
> This leads me to many papers, but not (in an obvious timesaving way) to
> implementations. Is there a specific implementation you had in mind
> that "delivers the performance goods?"
Chez Scheme uses an online polyvariance optimization. the SML compiler MLton
has a polyvariance pass.
--
jlouis
Ray Dillinger
> Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:
>
>
>>Ray Dillinger <be...@sonic.net> writes:
>>>http://www.newlisp.org/
>>>
>>>Warning; I haven't used the language much. I've just been
>>>looking around the lispy-language design space and it's one
>>>of the things I ran across.
>>For me it's a disaster.
>>Because of lack of GC there is no sharing of values:
> I just had a brief look at their FAQ, and it seems worse than a
> disaster.
As I said; it's limited, and there are some things you can't
express. There's a good reason I haven't used the language
much. But it is an interesting borderline case of an
implementation strategy, even though awful in some ways,
that lives without GC.
Bear
Ulrich Hobelmann
> False. In the presence of mutation, sharing is semantically significant.
IMHO Mutation is a reason NOT to share values, in order to avoid
subtle bugs.
>
>>At least it's an implementation thing that doesn't give you are real
>>features.
>
>
> <gnoring mutable state for a moment>
> Unless you consider being able to run the program on your
> computer (as opposed to not being able to do that) a feature. Without
> sharing, linear space requirements can turn into exponential space
> requirements.
> </gnoring mutable state for a moment>
Ok, that might be. I don't know how contrived those cases are and
how often they occur in practice.
>>>copied when passed as function arguments or put in data structures
>>
>>call-by-value is quite common...
>
>
> Quibble: This is not call-by-value. Scheme is call-by-value. Common
> Lisp is call-by-value. C is call-by-value. None of these language
> make deep copies of their arguments.
DEEP copies? Ok, that's obviously stupid...
When I want a deep copy, I can well specify and code that myself.
But in general... uuuh
Ulrich Hobelmann
> Ulrich Hobelmann <u.hob...@web.de> writes:
>
>
>>>Because of lack of GC there is no sharing of values: all values are
>>
>>sharing values is a (memory) efficiency hack ;)
>
>
> It's a significant efficiency hack. Without it a function which
> descends into a list using 'rest' takes O(N^2) time because each
> 'rest' copies the rest of the list.
But rest doesn't need to create a new list. Only if you want, say
a list filtered by some boolean function, and destroy the old
list, you have to create a new one.
Just like deep copying, I'm not saying everything should be copied
everywhere.
> The only way to pass mutable objects around in Newlisp is to make
> contexts. A context must be named with a symbol, and as far as I see
> you must invent unique symbols yourself.
That all sounds weird. I guess I won't use it, then...
>
>>>copied when passed as function arguments or put in data structures
>>
>>call-by-value is quite common...
>
>
> I find call-by-value which copies an arbitrary number of subobjects
> only in C++, which provides pointers to avoid copying.
Yes, I misread that one.
>>>ugly FFI which e.g. represents pointers as integers on the newLisp
>>>side (doesn't work when a pointer doesn't fit in C int), pointless
>>
>>Any 32bit platform, no?
>
>
> Yes, but what about 64bit platforms?
PPC can still use good old (32bit) lwz and stw, as it's one
architecture with just two different implementations ;)
Don't want huge pointers -> don't use those 64bit double-word
instructions.
Marcin 'Qrczak' Kowalczyk
>> It's a significant efficiency hack. Without it a function which
>> descends into a list using 'rest' takes O(N^2) time because each
>> 'rest' copies the rest of the list.
>
> But rest doesn't need to create a new list. Only if you want, say a
> list filtered by some boolean function, and destroy the old list, you
> have to create a new one.
rest in Newlisp does create a new list. There is no sharing of
substructures, it has no other choice than to copy it (together
with all list elements, e.g. if they are lists or arrays then
they are duplicated too).
CELL * p_rest(CELL * params)
{
CELL * cell;
CELL * tail;
[...]
tail->contents = (UINT)copyList(((CELL*)cell->contents)->next);
return(tail);
}
CELL * copyList(CELL * cell)
{
CELL * firstCell;
CELL * newCell;
if(cell == nilCell || cell == trueCell) return(lastCellCopied = cell);
firstCell = newCell = copyCell(cell);
while((cell = cell->next) != nilCell)
{
newCell->next = copyCell(cell);
newCell = newCell->next;
}
lastCellCopied = newCell;
return(firstCell);
}
The author of the language doesn't see this as a problem because
builtin functions like map or member wrap common tasks without the
overhead (they are implemented in C so they can use pointers to list
cells), and I think you can use imperative 'pop' to destructively
iterate through a list in O(N) total time.
The only sharing is indirect through symbols and contexts. Each symbol
is associated with a value or a context. A context maps symbols to
values. Other values than symbols and contexts are always physically
duplicated when passed as function arguments, stored in variables or
stored in data structures.
Contexts and symbols are deleted explicitly. Deleting a context
or a symbol changes all variables pointing to it to nil. This is
implemented by scanning all Newlisp's memory.
There are no local variables. 'let' actually temporarily changes the
binding in the current context (the current context is a global state)
and restores it at the end.
>> Yes, but what about 64bit platforms?
>
> PPC can still use good old (32bit) lwz and stw, as it's one
> architecture with just two different implementations ;)
>
> Don't want huge pointers -> don't use those 64bit double-word
> instructions.
I don't know PPC, but other 64-bit platforms like AMD64 and IA-64
have 64-bit pointers only.
Brandon J. Van Every
>
>Chez Scheme uses an online polyvariance optimization.
>
Good to know. Too bad I'd have to pay to play. Anyone know of good,
recent benchmarks for Chez Scheme? Googling I find old benchmarks.
These say little except that Petite Chez (freely available) is much
slower than Chez (needs a license).
>the SML compiler MLton has a polyvariance pass.
>
>
Thanks. I had thought about looking at the MLton sources, as once upon
a time I trundled through the ML realm before moving on to (possibly)
the Scheme universe. I didn't mention MLton since IIRC my original
question as Scheme-specific. Or at least, in c.l.s it should be. :-)
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
Brandon's Law (after Godwin's Law):
"As a Usenet discussion grows longer, the probability of
a person being called a troll approaches one RAPIDLY."
Jens Axel Søgaard
> Functional Programming makes many claims about how the world will be a
> better place if only we follow the paradigm. My question is, do
> compilers deliver this better world in practice? The main form of
> 'betterness' I'm interested in is performance. I'm interested in how
> functional recombination can produce blisteringly fast code, given the
> right compiler and the right problem domain.
This page is your friend:
<http://library.readscheme.org/page8.html>
especially the sections titled "Program Analysis, Inlining and
other Optimizations". The Olin Shivers papers (and his thesis)
is a good place to start.
--
Jens Axel Søgaard
Brandon J. Van Every
I'll check that paper out then.
I had previously started looking at some things on that page. Perhaps
someone gave me a reference to something on that page, or perhaps I
Googled it, I can't remember. I would note, however, that many of the
papers on that page are old. Knowledge doesn't have to go stale, but it
often does. In particular I do not trust papers written about the
performance characteristics of machines in the mid 90's or earlier. HW
has come a long way since then..
What I'd really like, as an adjunct to academic papers, is demonstrable
user-perceivable evidence of performance. A lot of papers say
this-or-that is great; where is the proof? That could be a request for
particular papers that are 'rather rigorous' about benchmarks, or for
independent benchmarks. Or for comparisons between real applications,
even if comparing apps is always problematic.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
"The pioneer is the one with the arrows in his back."
- anonymous entrepreneur
Matthias Buelow
>What I'd really like, as an adjunct to academic papers, is
>demonstrable user-perceivable evidence of performance. A lot of
>papers say this-or-that is great; where is the proof? That could be a
>request for particular papers that are 'rather rigorous' about
>benchmarks, or for independent benchmarks. Or for comparisons between
>real applications, even if comparing apps is always problematic.
What do you want? You're talking about games all the time. The point
is, there is no Scheme implementation atm. that you can use to write
the innards of a Doom3- or Source-style graphics engine and gain the
same performance as those engines. They're also the work of many many
man years and cannot be done by one person. So why this obsession
with extreme performance? Write your performance-sensitive stuff in
C, and bind it to a Scheme logics driver, which does the game "glue"
stuff.
mkb.
Jens Axel Søgaard
> I had previously started looking at some things on that page. Perhaps
> someone gave me a reference to something on that page, or perhaps I
> Googled it, I can't remember. I would note, however, that many of the
> papers on that page are old. Knowledge doesn't have to go stale, but it
> often does. In particular I do not trust papers written about the
> performance characteristics of machines in the mid 90's or earlier. HW
> has come a long way since then..
The majority of papers on that paper are hardware agnostic. Shivers's
work on 0CFA initiated a lot of research on flow control in functional
languages - something that previously were seen as "too difficult".
That is, to understand and judge new papers on the subject, you need to
know the classics first.
> What I'd really like, as an adjunct to academic papers, is demonstrable
> user-perceivable evidence of performance. A lot of papers say
> this-or-that is great; where is the proof? That could be a request for
> particular papers that are 'rather rigorous' about benchmarks, or for
> independent benchmarks. Or for comparisons between real applications,
> even if comparing apps is always problematic.
Then take a look at Dybvig's papers, they often describe the inner workings
of Chez Scheme.
Most often I find it is easier to read papers than code - there is less
details to distract one from the main lesson.
--
Jens Axel Søgaard
Brandon J. Van Every
>"Brandon J. Van Every" <mylastname...@mycompanyname.com> writes:
>
>
>
>>What I'd really like, as an adjunct to academic papers, is
>>demonstrable user-perceivable evidence of performance. A lot of
>>papers say this-or-that is great; where is the proof? That could be a
>>request for particular papers that are 'rather rigorous' about
>>benchmarks, or for independent benchmarks. Or for comparisons between
>>real applications, even if comparing apps is always problematic.
>>
>>
>
>What do you want?
>
What I want, is the rigor of demonstrable results. Not a lot of talk
about how things *should* perform in somebody's theory. I also don't
want continuous arguments about how I should just do such-and-such,
should just go implement such-and-such, should swallow Scheme-to-C, or
any other nonsense like that. My questions are about compiler design
and whether any of the performance promises of Functional Programming
are being realized in observable practice.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
20% of the world is real.
80% is gobbledygook we make up inside our own heads.
Brandon J. Van Every
> Brandon J. Van Every wrote:
>
>> I had previously started looking at some things on that page.
>> Perhaps someone gave me a reference to something on that page, or
>> perhaps I Googled it, I can't remember. I would note, however, that
>> many of the papers on that page are old. Knowledge doesn't have to
>> go stale, but it often does. In particular I do not trust papers
>> written about the performance characteristics of machines in the mid
>> 90's or earlier. HW has come a long way since then..
>
>
> The majority of papers on that paper are hardware agnostic. Shivers's
> work on 0CFA initiated a lot of research on flow control in functional
> languages - something that previously were seen as "too difficult".
> That is, to understand and judge new papers on the subject, you need to
> know the classics first.
Ok point taken.
>
>> What I'd really like, as an adjunct to academic papers, is
>> demonstrable user-perceivable evidence of performance. A lot of
>> papers say this-or-that is great; where is the proof? That could be
>> a request for particular papers that are 'rather rigorous' about
>> benchmarks, or for independent benchmarks. Or for comparisons
>> between real applications, even if comparing apps is always problematic.
>
>
> Then take a look at Dybvig's papers, they often describe the inner
> workings
> of Chez Scheme.
Ok dok.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
Does your Myers Briggs Type Indicator determine how you
debate? http://www.personalitypage.com/
Bruce Hoult
Sunnan <sun...@handgranat.org> wrote:
> That's not crazy if you're using (and properly debugging) a stack based
> language, like dc, forth or postscript.
Postscript *started* off as entirely stack-based (abeit multiple
independent stacks, such as the explicitly-managed save/restore one used
for fairly long-lived data), but from PostScript Level 2 moved to heap
based allocation for some things.
--
Bruce | 41.1670S | \ spoken | -+-
Hoult | 174.8263E | /\ here. | ----------O----------
Sunnan
> In article <zHPce.135945$dP1.4...@newsc.telia.net>,
> Sunnan <sun...@handgranat.org> wrote:
>
>
>>That's not crazy if you're using (and properly debugging) a stack based
>>language, like dc, forth or postscript.
>
>
> Postscript *started* off as entirely stack-based (abeit multiple
> independent stacks, such as the explicitly-managed save/restore one used
> for fairly long-lived data), but from PostScript Level 2 moved to heap
> based allocation for some things.
>
(which is also quirky due to its multiple "registers" idea).
Jesper Louis Andersen
> What I'd really like, as an adjunct to academic papers, is demonstrable
> user-perceivable evidence of performance.
You have to read the papers more in-depth then. One of the main aspects
is to demonstrate, with real-world programs, that said optimization benefits.
Therefore, one often has a set of benchmark programs for the language, not
entirely unlike the SPEC-benchmarks of C fame. These programs are to
demonstrate a performance change over a broad range of different kinds of
programs.
The advantage of the benchmark approach is the measurement aspect. It is not
possible to measure ``user-percieveable performance''. However, old benchmarks
may not be valid today due to hardware design changes, as you say. If the
paper is academic, you will have the hardware used for the benchmark stated.
This can be used to judge the benchmark in question.
I still think you are too focused on performance. My primary focus is ease
of development, then profiling and then performance.
--
jlouis
Brandon J. Van Every
>I still think you are too focused on performance. My primary focus is ease
>of development, then profiling and then performance.
>
>
>
People do what turns them on.
Adrian Kubala
> My questions are about compiler design and whether any of the
> performance promises of Functional Programming are being realized in
> observable practice.
The anecdotal evidence seems to suggest that whatever advantages are
gained in performance are immediately spent on abstraction or
correctness. If you tried to implement the kinds of designs you'd do in
a functional language in C, it would mostly be outright impossible, and
if not it would take way longer, perform worse and/or be buggier.
If you're looking for benchmarks that such-and-such well-known algorithm
can be compiled better from a functional language, it's not likely. What
you will find is programs which could *never* be written correctly in C,
and perform *well enough* to be useful, and that's the "performance
promise".
Anton van Straaten
> Sunnan wrote:
>
>> I've programmed plenty of dc and it's usually fine. You can have
>> memory leaks if you aren't careful - these are detected by printing
>> the stack every now and then, during the development process.
>
>
> I'm often pondering making a stack-based, non-gc:d interpreter for a
> very scheme-like language, to use for writing some tight parts of the
> hypothetical scheme based operating system we're all dreaming about.
Have you ever looked at Joy?
Overview: http://www.latrobe.edu.au/philosophy/phimvt/joy/forth-joy.html
Home page: http://www.latrobe.edu.au/philosophy/phimvt/joy.html
It's relevant to what you're describing, although it is partly gc'd,
because it relies on heap-based lists in order to implement first-class
functions.
Anton
Brandon J. Van Every
>If you're looking for benchmarks that such-and-such well-known algorithm
>can be compiled better from a functional language, it's not likely. What
>you will find is programs which could *never* be written correctly in C,
>and perform *well enough* to be useful, and that's the "performance
>promise".
>
>
Ok, that's a reasonable world view. It's not what I actually want,
which is why I find myself being driven to understand and possibly
extend / implement what I want, but at least it's a consistent
rationale. What I want is massive recombination of ASM instructions.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
Brandon's Law (after Godwin's Law):
Anton van Straaten
Have you looked at Appel's book "Compiling with Continuations"? CPS is
one of the better ways to do "massive recombination of ASM instructions"
at a relatively high level.
To quote Appel (beginning of Ch. 10): "CPS is meant to approximate the
operation of a Von Neumann computer; each operator of the former
corresponds to one (or at most a few) instructions of the latter."
The book describes an SML implementation, so it's not Scheme, but most
of the core principles are the same.
Anton
Sunnan
> Have you ever looked at Joy?
No, I haven't. Thank you.
> Overview: http://www.latrobe.edu.au/philosophy/phimvt/joy/forth-joy.html
> Home page: http://www.latrobe.edu.au/philosophy/phimvt/joy.html
>
> It's relevant to what you're describing, although it is partly gc'd,
> because it relies on heap-based lists in order to implement first-class
> functions.
Very nice. It seems to be more dc-like than forth. (In dc, just like in
Joy, you can put a list in square brackets on the stack and execute it
with x (it's i in Joy).)
dios_...@hotmail.com
> which is why I find myself being driven to understand and possibly
> extend / implement what I want, but at least it's a consistent
> rationale. What I want is massive recombination of ASM instructions.
LtU recently had a post about code volume vs. code paths following a
Power Law relationship. I think it isn't too much of a stretch to
suggest that your games will spent their times in a Power Law relation.
Heuristically, the Power Law is often called by "80/20 rule".
Given this, you can imagine that there is some amount of code with a
small domain that you would like to write in a language that compiles
to become very very quick. This can be done in C.
Then you have a long tail that will have loads of code that will not be
called all that often. You will want a language with moderate
performance requirements but very powerful expressivity to reduce your
time copying and pasting the same junk or what have you. Scheme can do
this. In fact, Scheme can become the foundation for a Domain Specific
Language for you to generate masses of code in this long tail with
virtually no effort to you.
For example, if you have a game with loads of objects you would like to
interact with, or even generating objects on the fly with properties
you also generate (e.g. if Pokemon *actually* bred monsters) then
Scheme would be good here. It would allow you to write a language that
can manage thousands of these objects -and those that haven't been
generated yet -in a coherent way. You could probably fold millions of
lines of code into thousands. This will save time for you so you can
spend more time tuning your program where it matters since you
obviously care a lot about speed.
That's pretty much what others have suggested but I thought it would
underline the advantage of mixing the languages. The idea that Scheme
might not have a Sufficiently Smart Compiler (TM) for the fast bits in
games is pretty much irrelevant to most people on this group.
gl hf
Brandon J. Van Every
>
> The idea that Scheme
>might not have a Sufficiently Smart Compiler (TM) for the fast bits in
>games is pretty much irrelevant to most people on this group.
>
>
I don't think most people in this group even know what 'games' are, or
could be, as applications. How about, for the class of games I'm
interested in, I use the terms 'massive simulation' or 'tough AI
problem' instead.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
20% of the world is real.
Andre
> That's pretty much what others have suggested but I thought it would
> underline the advantage of mixing the languages. The idea that Scheme
> might not have a Sufficiently Smart Compiler (TM) for the fast bits in
> games is pretty much irrelevant to most people on this group.
Replace "games" by "*" and I believe it is relevant to various
people on this group, not to mention the authors and users of
Schemes such as Bigloo, Stalin and Chez. It is hard to see
how Scheme will ever be taken seriously as anything other than
a toy language when the stock answer to questions about
performance is invariably to send the poster to C or assembly.
Brandon J. Van Every
>dios_...@hotmail.com wrote:
>
>
>
>>That's pretty much what others have suggested but I thought it would
>>underline the advantage of mixing the languages. The idea that Scheme
>>might not have a Sufficiently Smart Compiler (TM) for the fast bits in
>>games is pretty much irrelevant to most people on this group.
>>
>>
>
>Replace "games" by "*" and I believe it is relevant to various
>people on this group, not to mention the authors and users of
>Schemes such as Bigloo, Stalin and Chez.
>
Would you say Bigloo, Stalin, and Chez are pretty much "the landscape"
of performance oriented Scheme compilers?
>It is hard to see
>how Scheme will ever be taken seriously as anything other than
>a toy language when the stock answer to questions about
>performance is invariably to send the poster to C or assembly.
>
>
Well, without a big $$$$$$$$ marketing campaign that is. Microsoft does
it all the time with regards to C#. The whole philosophy is C# doesn't
do performance. It can be tied to Managed C++, which in turn can call
Native C++, which in turn can do all the usual optimization tricks.
Actually I think C# maybe can go to C via COM, skipping Managed C++, but
I can't remember. Anyways Microsoft compilation technologies are dead
boring from a performance standpoint. Their bread and butter is
accounting software. They try to put a marketing spin on C# for games,
with "Managed DirectX" and all of that. Last I looked at it maybe 1.5
years ago, the deeper I looked the sillier it all got. I made some
cat-calling posts in the Microsoft C# forums back then, asking about
Testimonials from commercial game developers about Managed DirectX's
efficacy. Nothing floated back but vague hints that maybe somebody was
doing something, and not even many of those. Nobody would stand up and
say, yeah, this stuff is da bomb. I think it's time to make another cat
call and see what floats back.
The Java universe has also been accounting driven / dead boring from a
performance standpoint. Hmm, 1 year ago Sun announced the Sun Games
Technology Group. What are they up to now?
http://www.sun.com/products-n-solutions/gametech/ seems to be their
webpage, which I had to Search for. I can't find by any straightforward
way from their main site. I would have expected to find it under
"Services & Solutions... Industry Solutions...
Media/Entertainment/Publishing" but that just ends in confusing mumbo
jumbo. There's also http://java.com/en/games/ but that appears to be
user rather than developer oriented.
Bottom line? If you've got enough money you can get people to use your
joke language for whatever. There's definitely a class of games that
don't require performance. I just don't happen to be interested in those.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
When no one else sells courage, supply and demand take hold.
Ewan
Unsuprisingly, Stalin and Bigloo compile to C. But that isn't the
point. The point is to have a domain specific language for the intended
domain. The code paths that need to be traversed often should be
written in a language that fascilitates fast code. Today, that means C
or Fortran. With more research it could mean Scheme, but the OP
specifically asked about what exists now.
What Scheme /does/ do well today is domain abstraction. Therefore your
long tail can be quite short in Scheme. It can be a big win for
programmer time.
Brandon J. Van Every
>Unsuprisingly, Stalin and Bigloo compile to C.
>
I am confused regarding Stalin. The latest README (Friday 10 March
2000) says the compiler is self-hosting. Quote: "Unlike previous
releases, this release does not require you to have Scheme->C. And it
does not require you to install Infrastructure or QobiScheme."
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
20% of the world is real.
Anton van Straaten
>
>> Unsuprisingly, Stalin and Bigloo compile to C.
>>
> I am confused regarding Stalin. The latest README (Friday 10 March
> 2000) says the compiler is self-hosting. Quote: "Unlike previous
> releases, this release does not require you to have Scheme->C. And it
> does not require you to install Infrastructure or QobiScheme."
Scheme->C is a different compiler which compiles, um, Scheme to C.
Apparently Stalin used to require it to build from scratch.
However, Stalin itself is also a Scheme to C compiler.
BTW, there are later versions of Stalin floating around. I've used
0.10alpha2, with README dated Jan 2003.
Anton
Brandon J. Van Every
>
> BTW, there are later versions of Stalin floating around. I've used
> 0.10alpha2, with README dated Jan 2003.
It seems that Jeffrey Mark Siskind's webpage
http://www.ece.purdue.edu/~qobi/software.html links to the older version
of Stalin. If you actually go to ftp://ftp.ecn.purdue.edu/qobi/ and
look at what's in the directory, you can find stalin0.10alpha2.tgz,
dated Jan 2003 as you say.
This sort of thing is but one instance of a "you're on your own"
philosophy. I last looked at Stalin in December. At the time I was
thinking in terms of tools that I could get other people to adopt, and
for that case use, such practices are unacceptable. Now I'm leaning
more towards compiler research and a number of things I've looked at in
the past, which didn't serve as examples of compelling tools, are much
more apropos from a research standpoint.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
"The pioneer is the one with the arrows in his back."
- anonymous entrepreneur
vermicule
> This sort of thing is but one instance of a "you're on your own"
> philosophy
That is how it is in the real world.
I have secretaries but if I goof up or if they f*&* up a delegated task,
blaming them doesnt fix the problem, I have to take the responsibility.
Sunnan
> of performance oriented Scheme compilers?
>
Brandon J. Van Every
> It seems that Jeffrey Mark Siskind's webpage
> http://www.ece.purdue.edu/~qobi/software.html links to the older
> version of Stalin. If you actually go to
> ftp://ftp.ecn.purdue.edu/qobi/ and look at what's in the directory,
> you can find stalin0.10alpha2.tgz, dated Jan 2003 as you say.
Which, unfortunately for my purposes, does not compile cleanly on Cygwin
like the earlier version does.
George Neuner
<fi...@my.address.elsewhere> wrote:
>Ulrich Hobelmann <u.hob...@web.de> writes:
>
>> Marcin 'Qrczak' Kowalczyk wrote:
>>> Because of lack of GC there is no sharing of values: all values are
>>> copied when passed as function arguments or put in data structures
>>
>> call-by-value is quite common...
>
>Quibble: This is not call-by-value. Scheme is call-by-value. Common
>Lisp is call-by-value. C is call-by-value. None of these language
>make deep copies of their arguments.
Pascal and many of it's variants and derivatives did perform a deep
copy unless the parameter was explictly designated to be passed by
reference.
I have no idea whether this is still the case in any of the modern
variants - Delphi, Oberon, Modula ?, etc.
George
--
for email reply remove "/" from address
Ray Dillinger
> Pascal and many of it's variants and derivatives did perform a deep
> copy unless the parameter was explictly designated to be passed by
> reference.
>
> I have no idea whether this is still the case in any of the modern
> variants - Delphi, Oberon, Modula ?, etc.
Still true. If you don't pass an array "var", the system will
make a copy of the array to be a local variable in the called
function.
And not a bad thing; it makes certain kinds of recursive problems
with state expressible as an array very easy to work with and
do backtracking with. It's nice, for example, for implementing
a backtracking parser. (of course, with a backtracking parser,
you want heavy memoization anyway, but that's compatible...)
Bear
Marcin 'Qrczak' Kowalczyk
>>Quibble: This is not call-by-value. Scheme is call-by-value. Common
>>Lisp is call-by-value. C is call-by-value. None of these language
>>make deep copies of their arguments.
>
> Pascal and many of it's variants and derivatives did perform a deep
> copy unless the parameter was explictly designated to be passed by
> reference.
The amount to copy is still a compile time constant. If you want a
structure with a dynamically determined size, you have to use pointers.
Their referents are not automatically copied, although copying only
the header record which holds the pointers would be generally a bad
idea, and you prefer to not copy any part of it at all.
The only language I know which deeply copies data structures when they
are passed as arguments or stored in other data structures, besides
Newlisp, is C++. The implementor of a data structure must define how
it should be copied, but copying is implicit on the client side.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk
>>Quibble: This is not call-by-value. Scheme is call-by-value. Common
>>Lisp is call-by-value. C is call-by-value. None of these language
>>make deep copies of their arguments.
>
> Pascal and many of it's variants and derivatives did perform a deep
> copy unless the parameter was explictly designated to be passed by
> reference.
The amount to copy is still a compile time constant. If you want a
structure with a dynamically determined size, you have to use pointers.
Their referents are not automatically copied, although copying only
the header record which holds the pointers would be generally a bad
idea, and you prefer to not copy any part of it at all.
The only language I know which deeply copies data structures when they
are passed as arguments or stored in other data structures, besides
Newlisp, is C++. The implementor of a data structure must define how
it should be copied, but copying is implicit on the client side.
But C++ allows to pass values by reference too. Newlisp doesn't.
George Neuner
<qrc...@knm.org.pl> wrote:
>George Neuner <gneuner2/@comcast.net> writes:
>
>>>Quibble: This is not call-by-value. Scheme is call-by-value. Common
>>>Lisp is call-by-value. C is call-by-value. None of these language
>>>make deep copies of their arguments.
>>
>> Pascal and many of it's variants and derivatives did perform a deep
>> copy unless the parameter was explictly designated to be passed by
>> reference.
>
>The amount to copy is still a compile time constant. If you want a
>structure with a dynamically determined size, you have to use pointers.
I'm not sure about that. Modula 2 apparently allows for passing open
arrays by value - at least syntactically. At a glance Modula 3 syntax
for open array parameters appears to be the same.
But I've never peeked under the hood.
Ray Blaak
> George Neuner wrote:
> > I have no idea whether this is still the case in any of the modern
> > variants - Delphi, Oberon, Modula ?, etc.
>
> Still true. If you don't pass an array "var", the system will
> make a copy of the array to be a local variable in the called
> function.
Actually, in Delphi, "open array" parameters perform stack copying, e.g.
procedure ChangeIt(val : array of Integer);
begin
val[0] := 1; // will not affect caller's element.
end;
Dynamic arrays on the other hand, are allocated dynamically, and do not cause
implicit stack copying, e.g.
type Arr = array of Integer;
procedure ChangeIt2(val : Arr);
begin
val[0] := 2; // this will change the caller's 0th element
end;
On yet the other hand, if one passes a value of type Arr to ChangeIt, then the
value *is* copied locally on the stack.
Wierd. I prefer Java's or C#'s consistent and easy-to-understand approach.
> And not a bad thing; it makes certain kinds of recursive problems
> with state expressible as an array very easy to work with and
> do backtracking with.
That still can be done by explicitly copying the array when needed. More
tedious to be sure, but at least less confusing than Delphi's open vs dynamic
array situation.
--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
rAYb...@STRIPCAPStelus.net The Rhythm has my soul.
Matthias Blume
> George Neuner wrote:
>
>> Pascal and many of it's variants and derivatives did perform a deep
>> copy unless the parameter was explictly designated to be passed by
>> reference.
>> I have no idea whether this is still the case in any of the modern
>> variants - Delphi, Oberon, Modula ?, etc.
>
> Still true. If you don't pass an array "var", the system will
> make a copy of the array to be a local variable in the called
> function.
But that wouldn't be a /deep/ copy.
Matthias Blume
> On Sun, 01 May 2005 00:57:48 -0500, Matthias Blume
> <fi...@my.address.elsewhere> wrote:
>
>>Ulrich Hobelmann <u.hob...@web.de> writes:
>>
>>> Marcin 'Qrczak' Kowalczyk wrote:
>>>> Because of lack of GC there is no sharing of values: all values are
>>>> copied when passed as function arguments or put in data structures
>>>
>>> call-by-value is quite common...
>>
>>Quibble: This is not call-by-value. Scheme is call-by-value. Common
>>Lisp is call-by-value. C is call-by-value. None of these language
>>make deep copies of their arguments.
>
> Pascal and many of it's variants and derivatives did perform a deep
> copy unless the parameter was explictly designated to be passed by
> reference.
No, they didn't. They copy the top-level array or record. They do
/not/ make /deep/ copy.
Matthias