Hi all,
Have I correctly concluded that it is impossible for a /single stack/
function interface to return an arbitrary number of values without consing?
My reasoning is thus:
1. The function caller places n arguments on the stack and informs the
function callee of their location and number. No problem so far.
2. The callee then reserves space on the stack "above" the arguments for
local lexical variables. The amount of space to reserve can be accurately
determined at compile time. Still no problem.
3. The number of values the callee returns may only be known at run time,
and crucially may only be known by the callee once it is time to return to
the caller. This is too late to reserve space on the stack when the caller
may itself call a function before returning. At the time it calls a
subfunction the callee needs to allocate space for its arguments. But it
can't allocate the arguments when it doesn't know how much space to
reserve for multiple return values.
Maintaining two stacks--one for arguments and local variables and the
other for multiple return values--seems natural but costly.
Another potential solution would be to only support a low number of
multiple return values, such as the minimum of 20 as specified by ANSI
Common Lisp (multiple-values-limit). At steps 1, 2 or 3 one would always
reserve space for up to 20 return values.
Has anyone ever found it useful to return more than a few multiple return
values? If you knew your implementation never consed multiple return
values would you start returning hundreds or thousands of values this way?
Or would you still just pass them by reference via, e.g. an array or list?
Regards,
Adam
From: Duane Rettig
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <47jm09jys.fsf@franz.com>
Adam Warner <······@consulting.net.nz> writes:
> Hi all,
>
> Have I correctly concluded that it is impossible for a /single stack/
> function interface to return an arbitrary number of values without consing?
It depends on what your definition of "consing" is. "Stack consing"
might still be considered consing, depending on what you are trying
to measure. Also, "resourcing" might also be considered consing,
because it uses memory resources. Under that broader interpretation,
not only are you correct, but I would say even more strongly that it
is impossible to return more than one value without consing under _any_
circumstances. Note that the third usage of the glossary term for
"cons" is aligned with this broader interpretation, because it does
not distinguish between storage kinds in its description.
But if we stick with the more traditional use of the word consing,
where memory used must be dealt with and possibly discarded by the
garbage collector, then there are many ways around the problem,
including ones that have been mentioned.
When I first did a port of Franz Lisp (no, not Allegro CL, and I
wan't even working for Franz Inc at the time) to the Amdahl UTS
(an IBM 370 compatible), I tried to implement the multiple value
returns as was suggested by Frode. This did not work well, because
the 370 architecture didn't take kindly to arbitrary movement of
the stack pointer. But, as Frode suggested, it works as a
proof-of-concept that values returned can be consed on the stack,
even at run-time.
In Allegro CL, we take a two-fold approach:
1. For all architectures that have free registers for passing
N arguments, we pass the first N values back in those same
registers. This includes the x86, for which we devised a Lisp
calling sequence that uses eax/edx to pass the first two args in
registers, and it also includes the AMD64, where they did the
sensible thing and prescribed 6 registers for arguments, so we
return 2 and 6 values in those same registers, respectively, in
those architectures. However, it does _not_ include the Sparc,
whose standard calling sequence uses register windows, and which
uses a trick to even get the normal single return value passed
upward through the windows - for the sparc (both 32 and 64 bits)
we only return the first value in a register. All other RISC
architectures, like the x86/AMD, have a certain number of arg
registers, and we return values in those same registers.
2. For values that exceed the maximum number of values returned
in registers, we use resources called values-vectors. These vectors
are now actually a distinguished type, and are allocated as needed
as a resource. There is almost always at least one values-vector
sitting in the resource pool, so there is seldom a need to allocate
more. The only other time allocation is necessary is when the
number of values returned will exceed the size of the resourced
values-vector.
> My reasoning is thus:
[ ... ]
You assume two implementations, but they aren't necessarily
the only possible ones.
> Another potential solution would be to only support a low number of
> multiple return values, such as the minimum of 20 as specified by ANSI
> Common Lisp (multiple-values-limit). At steps 1, 2 or 3 one would always
> reserve space for up to 20 return values.
Yes, this is possible, but it does limit the application of "arbitrary"
values returned.
> Has anyone ever found it useful to return more than a few multiple return
> values? If you knew your implementation never consed multiple return
> values would you start returning hundreds or thousands of values this way?
Looking at common usage, one value returned is by far the norm. I would
guess that there is a distribution curve that has an extremely high
negative slope, and which gets close to zero at 20. I see a significant
number of 2-valued functions in CL. Of course, the *-information functions
I am working on in the Environments Access module each return up to several
values, on average, 3 or 4.
If you are looking for _portable_ coding, never exceed 20 values returned.
But perhaps, on a per-implementation basis, and depending on whether they
cons or not for those counts.
> Or would you still just pass them by reference via, e.g. an array or list?
It is dangerous to consider the carrying of data within arrays or lists
as "pass by reference". If you do, then you must reconcile what
DELETE does, with respect to this terminology - is DELETE "passing by
reference"?
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig wrote:
> 2. For values that exceed the maximum number of values returned
> in registers, we use resources called values-vectors. ...
Duane has related how ACL accomplishes non-consing multiple values,
but that isn't the only way it _could_ be done. It is instructive
to think about other mechanisms because it instructs the user
programmer that he can't always make assumptions about the behavior
of the implementation based on the naive model of Lisp execution.
(Nor for other languages.)
In most circumstances where multiple values are received by a
calling function, the maximum number of values can be received is
manifest in the code. For multiple-value-bind, it is the number
of binding variables. For nth-value, it is N (if N can be
determined at compile time). For multiple-value-list the limit
cannot be ascertained (unless the definition of the called function
is known at compile time) but in that case the list must usually
be consed as a first-class object anyway, so execution without
consing is not an issue.
If the maximum number of interesting return values is known, then
the implementaation can stack-allocate suficient space, and
communicate the size of that space to the called function. If
that communication is too inefficient at runtime, then the
implementation could alternatively always allocate enough
space for cl:multiple-values-limit, which can legally be as
small as 20.
The important point here is that consing is not a sensible
property ni ANSI CL, yet implemenations do strange and magical
things to eliminate consing in important situations found in
typical code.
Hmm, I wonder if any implementation stack conses in this case:
(let ((foo (multiple-value-list ...)))
(declare (dynamic-extent foo))
...)
On Thu, 27 Jan 2005 06:10:26 +0000, Steven M. Haflich wrote:
> If the maximum number of interesting return values is known, then the
> implementation can stack-allocate sufficient space, and communicate the
> size of that space to the called function. If that communication is too
> inefficient at runtime, then the implementation could alternatively
> always allocate enough space for cl:multiple-values-limit, which can
> legally be as small as 20.
Many thanks for your replies Duane, Steven, Barry and all. Before reading
either of Barry or Steven's replies about this approach I implemented it
today in portable C (ISO C99). I am communicating the size of the return
space at runtime (of type ptrdiff_t, which may be a little over the top:
that's signed 32-bits on IA32 and signed 64-bits on AMD64. The AMD64
optimisation guide states that "The preferred type for array indices is
ptrdiff_t." int32_t might be a better choice for the stack index. I
believe the point is that one should avoid unsigned array indices).
I benchmarked my test stack against a worst case scenario:
#include <stdint.h>
int32_t test_recursion_benchmark(int32_t n) {
if (n==1) {
return 1;
} else {
int32_t ret=n+test_recursion_benchmark(n-1);
return ret;
}
}
And found my test stack was 230 times slower when compiled with GCC at -O2
optimisation :-) But it wasn't much slower when both were compiled at
-O0. GCC performs a tail call optimisation on the above code at -O2.
Regards,
Adam
Adam Warner wrote:
> Have I correctly concluded that it is impossible for a /single stack/
> function interface to return an arbitrary number of values without consing?
In this paper Ashley and Dybvig discuss the problem of implementing
multiple return values in Scheme. Despite the title, they also
explain how their technique can be adapted to implement Common Lisp's
multiple value interface:
J. Michael Ashley and R. Kent Dybvig.
"An Efficient Implementation of Multiple Return Values in Scheme".
1994 ACM Conference on LISP and Functional Programming. June 1994.
<http://repository.readscheme.org/ftp/papers/jmashley/lfp94.pdf>
This paper was found using readscheme.org:
<http://library.readscheme.org/page8.html>
--
Jens Axel Søgaard
From: Frode Vatvedt Fjeld
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <2hr7k8cu4h.fsf@vserver.cs.uit.no>
Adam Warner <······@consulting.net.nz> writes:
> Have I correctly concluded that it is impossible for a /single
> stack/ function interface to return an arbitrary number of values
> without consing?
I believe this is wrong. It's trivial for the callee to e.g. push each
return value, then the number of values, and then to return. The
caller pops off the number of values and then each actual value. This
is very inefficient, but works as a proof of concept.
Actually I wrote a system somewhat like this once, except it was made
quite efficient by the fact that the number of values was returned in
a register, and the stack-pointer was reset by the callee before
returning (leaving the multiple return values below the
stack-pointer), such that the caller could just ignore the issue in
the common case that it requested a single value. This worked quite
well, with one crucial exception: if an (hardware) interrupt occurred
at the wrong time (and the interrupt handler used the same stack), the
return values below the stack-pointer would get overwritten. Which was
why I abandoned this stack-based scheme and started using a
per-thread, fixed-size, pre-allocated buffer for multiple values.
--
Frode Vatvedt Fjeld
On Wed, 26 Jan 2005 12:22:38 +0100, Frode Vatvedt Fjeld wrote:
> Adam Warner <······@consulting.net.nz> writes:
>
>> Have I correctly concluded that it is impossible for a /single
>> stack/ function interface to return an arbitrary number of values
>> without consing?
>
> I believe this is wrong. It's trivial for the callee to e.g. push each
> return value, then the number of values, and then to return. The
> caller pops off the number of values and then each actual value. This
> is very inefficient, but works as a proof of concept.
(defun make-random-list ()
(make-list (random 21) :initial-element 42))
(defun arbitrary-return-values ()
(values-list (make-random-list)))
arbitrary-return-values is the primary function.
An implication of your proof of concept is that space for the multiple
return values doesn't need to be allocated at the start of the primary
function call. It can be allocated after nested functions have returned
their values. I now remember why I (probably incorrectly) overlooked the
approach:
A potential generalisation of the above code (with the stack growing down):
+---------------+
| Primary args/ |
|Local variables|
+---------------+
|Nested fn args/|
|Local variables|
+---------------+
| Nested return |
| values |
+---------------+
| Primary fn |
| return values |
+---------------+
This appears to have negative garbage collection implications. At the
time the primary return values are being constructed from the nested
return value(s) the nested function's arguments and local variables are
still on a live portion of the stack. For more precise collection I'd like
to move the stack pointer up before handling the nested return values. It
appears I can only do this if (a) the return values are allocated before
the args/local variables; or (b) the return values are allocated on a
separate stack.
Is it possible to implement non-consing multiple return values in a single
stack Lisp with very precise collection? Would there be any practical
advantage to this extra precision (enough to recommend a second stack)?
[Where the garbage collector follows pointers from the live portion of a
stack into the heap]
> Actually I wrote a system somewhat like this once, except it was made
> quite efficient by the fact that the number of values was returned in a
> register, and the stack-pointer was reset by the callee before returning
> (leaving the multiple return values below the stack-pointer), such that
> the caller could just ignore the issue in the common case that it
> requested a single value. This worked quite well, with one crucial
> exception: if an (hardware) interrupt occurred at the wrong time (and
> the interrupt handler used the same stack), the return values below the
> stack-pointer would get overwritten. Which was why I abandoned this
> stack-based scheme and started using a per-thread, fixed-size,
> pre-allocated buffer for multiple values.
I've read about these kinds of problems. That's such a pity. Thanks for
the info Frode (likewise Jens).
Regards,
Adam
From: Bruno Haible
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <ct89j5$9qh$1@laposte.ilog.fr>
Adam Warner asked:
>
> Have I correctly concluded that it is impossible for a /single stack/
> function interface to return an arbitrary number of values without consing?
No. Try CLISP. It has a single stack for objects; the C stack doesn't
count here since it cannot hold Lisp objects. Here is a session that shows
zero consing despite use of multiple values through funcall, catch,
return-from.
[1]> (defun make-random-values ()
(case (random 5)
(0 (values 42))
(1 (values 42 42 42 42 42))
(2 (values 42 42 42 42 42 42 42 42 42 42))
(3 (values 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42))
(4 (values 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42))))
MAKE-RANDOM-VALUES
[2]> (defun arbitrary-return-values ()
(make-random-values))
ARBITRARY-RETURN-VALUES
[3]> (defun another-func ()
(if (oddp 7)
(catch '66
(block nil
(return-from nil
(funcall #'(lambda () (arbitrary-return-values))))))))
ANOTHER-FUNC
[4]> (compile 'another-func)
ANOTHER-FUNC ;
NIL ;
NIL
[5]> (times (another-func))
Permanent Temporary
Class instances bytes instances bytes
----- --------- --------- --------- ---------
----- --------- --------- --------- ---------
Total 0 0 0 0
Real time: 2.5E-5 sec.
Run time: 0.0 sec.
Space: 0 Bytes
42 ;
42 ;
42 ;
42 ;
42
Bruno
From: Duane Rettig
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <4brbc9mjb.fsf@franz.com>
Bruno Haible <·····@clisp.org> writes:
> Adam Warner asked:
> >
> > Have I correctly concluded that it is impossible for a /single stack/
> > function interface to return an arbitrary number of values without consing?
>
> No. Try CLISP. It has a single stack for objects; the C stack doesn't
> count here since it cannot hold Lisp objects. Here is a session that shows
> zero consing despite use of multiple values through funcall, catch,
> return-from.
Heh; Allegro CL doesn't cons here, either:
CL-USER(1): (defun make-random-values ()
(case (random 5)
(0 (values 42))
(1 (values 42 42 42 42 42))
(2 (values 42 42 42 42 42 42 42 42 42 42))
(3 (values 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42))
(4 (values 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42))))
MAKE-RANDOM-VALUES
CL-USER(2): (compile *)
MAKE-RANDOM-VALUES
NIL
NIL
CL-USER(3): (defun arbitrary-return-values ()
(make-random-values))
ARBITRARY-RETURN-VALUES
CL-USER(4): (compile *)
ARBITRARY-RETURN-VALUES
NIL
NIL
CL-USER(5): (defun another-func ()
(if (oddp 7)
(catch '66
(block nil
(return-from nil
(funcall #'(lambda () (arbitrary-return-values))))))))
ANOTHER-FUNC
CL-USER(6): (compile *)
ANOTHER-FUNC
NIL
NIL
CL-USER(7): (time (another-func))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
42
42
42
42
42
CL-USER(8): (time (another-func))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
42
42
42
42
42
42
42
42
42
42
42
42
42
42
42
CL-USER(9): (time (another-func))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
42
42
42
42
42
CL-USER(10): (time (another-func))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
42
CL-USER(11): (time (another-func))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
42
42
42
42
42
CL-USER(12):
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: Wade Humeniuk
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <BNPJd.6$CI5.3@clgrps12>
Duane Rettig wrote:
>
>
> Heh; Allegro CL doesn't cons here, either:
>
Either does LW:
CL-USER 10 > (time (another-func))
Timing the evaluation of (ANOTHER-FUNC)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
42
CL-USER 11 >
Wade
From: Svein Ove Aas
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <ct94r3$18$1@services.kq.no>
start quoting Wade Humeniuk :
> Duane Rettig wrote:
>
>>
>>
>> Heh; Allegro CL doesn't cons here, either:
>>
>
> Neither does LW:
>
*snip*
You should be aware that, in SBCL at least, consing seems to be counted by
page allocations or some other higher granularity, so I suspect that
calling time like that is unlikely to report any space allocations. (Try
running a non-consing loop over it 10,000 times or so.)
If this isn't the case for ACL or Lispworks, then your conclusions are of
course correct. (And it would be nice to know how they do it)
From: Wade Humeniuk
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <H_XJd.153762$KO5.625@clgrps13>
Svein Ove Aas wrote:
>
> You should be aware that, in SBCL at least, consing seems to be counted by
> page allocations or some other higher granularity, so I suspect that
> calling time like that is unlikely to report any space allocations. (Try
> running a non-consing loop over it 10,000 times or so.)
>
> If this isn't the case for ACL or Lispworks, then your conclusions are of
> course correct. (And it would be nice to know how they do it)
CL-USER 11 > (defun another-func-10000 ()
(loop repeat 10000 do (another-func)))
ANOTHER-FUNC-10000
CL-USER 12 > (compile *)
ANOTHER-FUNC-10000
NIL
NIL
CL-USER 13 > (time (another-func-10000))
Timing the evaluation of (ANOTHER-FUNC-10000)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
NIL
Wade