From: Kenny Tilton
Subject: Which is faster, typep or method dispatch on type?
Date:
Message-ID: <3C06B067.2C6942E9@nyc.rr.com>
I coulda swore I read an article on this NG explaining that typep was
relatively slow compared to method dispatch, so that rather than code:
(when (typep x 'number)
(do-a-number x)) ;; do-a-number here can be a defun
it would be a hair faster to make do-a-number into a GF and specialize
on number and an NOP unspecialized or t method.
But in the recent benchmarking of defun vs defmethod i threw in a
version doing type and that came out faster than the method. I guess
that makes it clear I have something wrong, but I thought I'd check in
here for a confirm.
thx,
kenny
clinisys
From: Dave Morse
Subject: Re: Which is faster, typep or method dispatch on type?
Date:
Message-ID: <3C06CD9A.5020104@bomberlan.net>
Kenny Tilton wrote:
> I coulda swore I read an article on this NG explaining that typep was
> relatively slow compared to method dispatch, so that rather than code:
>
> (when (typep x 'number)
> (do-a-number x)) ;; do-a-number here can be a defun
>
> it would be a hair faster to make do-a-number into a GF and specialize
> on number and an NOP unspecialized or t method.
>
> But in the recent benchmarking of defun vs defmethod i threw in a
> version doing type and that came out faster than the method. I guess
> that makes it clear I have something wrong, but I thought I'd check in
> here for a confirm.
Implementation dependant.
>>>>> "Dave" == Dave Morse <······@bomberlan.net> writes:
Dave> Implementation dependant.
I seem to have heard that CMUCL has a very efficient `typep'.
------------------------+-----------------------------------------------------
Christian Lynbech | Ericsson Telebit, Skanderborgvej 232, DK-8260 Viby J
Phone: +45 8938 5244 | email: ·················@ted.ericsson.dk
Fax: +45 8938 5101 | web: www.ericsson.com
------------------------+-----------------------------------------------------
Hit the philistines three times over the head with the Elisp reference manual.
- ·······@hal.com (Michael A. Petonic)
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Christian Lynbech <·················@ted.ericsson.dk> writes:
>
> > >>>>> "Dave" == Dave Morse <······@bomberlan.net> writes:
> >
> > Dave> Implementation dependant.
> >
> > I seem to have heard that CMUCL has a very efficient `typep'.
>
> Wow, no kidding. Check out what this TYPEP compiled to:
(On a less silly note, this isn't a completely unreasonable example.
If the function that does typep is declared inline, there are a lot of
times when this kind of static analysis produces code that doesn't do
any actual type checking)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> ···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > Christian Lynbech <·················@ted.ericsson.dk> writes:
> >
> > > >>>>> "Dave" == Dave Morse <······@bomberlan.net> writes:
> > >
> > > Dave> Implementation dependant.
> > >
> > > I seem to have heard that CMUCL has a very efficient `typep'.
> >
> > Wow, no kidding. Check out what this TYPEP compiled to:
>
> (On a less silly note, this isn't a completely unreasonable example.
> If the function that does typep is declared inline, there are a lot of
> times when this kind of static analysis produces code that doesn't do
> any actual type checking)
And, by contrast, if the type is not known, one usually finds TYPEP starting
by looking up the type at runtime to see if it's been DEFTYPE'd, etc.
before falling back to checking for it being a primitive class. Whereas,
at minimum, even with no real type "optimization", a compiled TYPEP for
something known to be a class can skip the first step. I think that's the
root of why people often say they expect TYPEP to be slower than GF's.
Kent M Pitman <······@world.std.com> writes:
> And, by contrast, if the type is not known, one usually finds TYPEP starting
> by looking up the type at runtime to see if it's been DEFTYPE'd, etc.
> before falling back to checking for it being a primitive class. Whereas,
> at minimum, even with no real type "optimization", a compiled TYPEP for
> something known to be a class can skip the first step. I think that's the
> root of why people often say they expect TYPEP to be slower than GF's.
In fact, for the class case, the type check can be reduced to two
loads and a compare, see:
@inproceedings {vitek97efficient,
author = "Jan Vitek and R. Nigel Horspool and Andreas Krall",
title = "Efficient type inclusion tests",
booktitle = "Proceedings of the Conference on Object-Oriented Programming,
Systems, Languages, and Application, OOPSLA'97",
month = "October",
year = 1997,
address = "Atlanta, GA",
publisher = "ACM Press"
}
This trick should be applicable to CLOS.
GF dispatch, on the other hand, requires two loads per argument and a
call:
@article {dujardin96fast,
author = "Eric Dujardin and Eric Amiel and Eric Simon",
title = "Fast algorithms for compressed multimethod dispatch table
generation",
note = "Originally written in 1996",
journal = "ACM Transactions on Programming Languages and Systems",
volume = 20,
number = 1,
year = 1998,
pages = "116--165",
}
@inproceedings {vitek96compact,
author = "Jan Vitek and R. Nigel Horspool",
title = "Compact dispatch tables for dynamically typed programming
languages",
booktitle = "Proceedings of the International Conference on Compiler
Construction",
year = 1996
}
Unfortunately neither CLOS nor Dylan can make real use of these
tricks, mainly because of the dependence of sorted-applicable-methods
on the actual order of arguments, but also because of all the weird
non-class types in Dylan.
So I'm not sure about any CL implementation, but I'd argue that TYPEP
can be made faster than GF dispatch if it is known at compile time
that we're dealing with the class case.
In hindsight, it wouldn't have costed Dylan anything to go for real
predicate dispatch, which is even more powerful than type-based GF
dispatch.
Anfdreas
--
"In my eyes it is never a crime to steal knowledge. It is a good
theft. The pirate of knowledge is a good pirate."
(Michel Serres)
From: Kenny Tilton
Subject: Re: Which is faster, typep or method dispatch on type?
Date:
Message-ID: <3C079FFF.E12A1E61@nyc.rr.com>
Kent M Pitman wrote:
>
> And, by contrast, if the type is not known, one usually finds TYPEP starting
> by looking up the type at runtime to see if it's been DEFTYPE'd, etc.
> before falling back to checking for it being a primitive class. Whereas,
> at minimum, even with no real type "optimization", a compiled TYPEP for
> something known to be a class can skip the first step. I think that's the
> root of why people often say they expect TYPEP to be slower than GF's.
Bingo. That is what I remembered:
"...looking up the type at runtime to see if it's been DEFTYPE'd,
etc..."
...and did not remember:
"...if the type is not known".
Jeez, a lifetime of avoiding 'typep...for nil! :)
I gather this is also implementation dependent, what if anything can in
general be said about:
"a compiled TYPEP for something known to be a class can skip the first
step"
Is it something like this:
(typep x typeargument) cannot be optimized
(typep x 'number) will always be optimized
(typep x 'myclass) will be optimized if the compiler has seen a
defclass.... well, no, what if that class is not loaded at run-time?
kenny
clinisys
kenny
clinisys
Kenny Tilton <·······@nyc.rr.com> writes:
> I gather this is also implementation dependent, what if anything can in
> general be said about:
>
> "a compiled TYPEP for something known to be a class can skip the first
> step"
>
> Is it something like this:
>
> (typep x typeargument) cannot be optimized
>
> (typep x 'number) will always be optimized
>
> (typep x 'myclass) will be optimized if the compiler has seen a
> defclass.... well, no, what if that class is not loaded at run-time?
probably "might be" not "will always be".
implementational freedom and all that. but also the right of implementations
to experiment with different degrees of redefinability.
From: ·······@andrew.cmu.edu
Subject: Re: Which is faster, typep or method dispatch on type?
Date:
Message-ID: <20011130144131.C2173@emu>
On Fri, Nov 30, 2001 at 03:09:21AM -0800, Thomas F. Burdick wrote:
>
> Wow, no kidding. Check out what this TYPEP compiled to:
>
> * (defun foo ()
> (declare (optimize (speed 3) (safety 0)))
> (typep (+ 1 1) 'number))
>
> FOO
> * (compile 'foo)
> Compiling LAMBDA NIL:
> Compiling Top-Level Form:
>
> FOO
> NIL
> NIL
> * (disassemble #'foo)
> 400755C8: .ENTRY FOO() ; (FUNCTION NIL (MEMBER T))
> 5E0: ADD -18, %CODE
> 5E4: ADD %CFP, 32, %CSP
> 5E8: ADD %NULL, 28, %A0 ; No-arg-parsing entry point
> 5EC: MOV %CFP, %CSP
> 5F0: MOV %OCFP, %CFP
> 5F4: J %LRA+5
> 5F8: MOV %LRA, %CODE
> 5FC: UNIMP 0
>
> And compare it to the code produced for this similar function!
>
> * (defun bar ()
> (declare (optimize (speed 3) (safety 0)))
> (+ 1 1) t)
> BAR
> * (compile 'bar)
> Compiling LAMBDA NIL:
> Compiling Top-Level Form:
>
> BAR
> NIL
> NIL
> * (disassemble #'bar)
> 400A5080: .ENTRY BAR() ; (FUNCTION NIL (MEMBER T))
> 98: ADD -18, %CODE
> 9C: ADD %CFP, 32, %CSP
> A0: ADD %NULL, 28, %A0 ; No-arg-parsing entry point
> A4: MOV %CFP, %CSP
> A8: MOV %OCFP, %CFP
> AC: J %LRA+5
> B0: MOV %LRA, %CODE
> B4: UNIMP 0
>
> (Sorry, it's my sense of humor, I couldn't help it)
>
* (describe '+)
+ is an external symbol in the COMMON-LISP package.
It is a special variable; its value is NIL.
Special documentation:
Holds the value of the most recent top-level READ.
Function: #<Function + {10270269}>
Function arguments:
(&rest args)
Function documentation:
Returns the sum of its arguments. With no args, returns 0.
Its declared argument types are:
(&REST NUMBER)
Its result type is:
NUMBER
Given that, and CMUCL's reputation for type inference ability, I'd be
highly disappointed if it didn't optimize it away immediately.
--
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Matthew Danish email: ·······@andrew.cmu.edu ;;
;; OpenPGP public key available from: 'finger ···@db.debian.org' ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
From: Robert Monfera
Subject: Re: Which is faster, typep or method dispatch on type?
Date:
Message-ID: <3C07D32E.2060700@fisec.com>
(defun bar ())
(defun foo ()
(declare (optimize (speed 3) (safety 0)))
(typecase (the fixnum 5)
(fixnum 5)
(double-float (bar))))
Compilers should generate the same result as for this (not because 5 is
a literal, but because typecase can be optimized away due to the type
declaration):
(defun foo ()
(declare (optimize (speed 3) (safety 0)))
5)
Robert
Thomas F. Burdick wrote:
> Christian Lynbech <·················@ted.ericsson.dk> writes:
>
>
>>>>>>>"Dave" == Dave Morse <······@bomberlan.net> writes:
>>>>>>>
>>Dave> Implementation dependant.
>>
>>I seem to have heard that CMUCL has a very efficient `typep'.
>>
>
> Wow, no kidding. Check out what this TYPEP compiled to:
>
> * (defun foo ()
> (declare (optimize (speed 3) (safety 0)))
> (typep (+ 1 1) 'number))
Robert Monfera <·······@fisec.com> writes:
> (defun bar ())
>
> (defun foo ()
> (declare (optimize (speed 3) (safety 0)))
> (typecase (the fixnum 5)
> (fixnum 5)
> (double-float (bar))))
>
> Compilers should generate the same result as for this (not because 5
> is a literal, but because typecase can be optimized away due to the
> type declaration):
>
> (defun foo ()
> (declare (optimize (speed 3) (safety 0)))
> 5)
Actually, I was trying to humorously show what can happen with CMUCL's
type inference. Sure, explicit type declarations all over the place
can speed things up, but my code doesn't look like that. With CMUCL,
though just a few declarations here and there (letting the compiler
know, for example, that + returns a number) can have far-reaching
effects. And this obviously type inference affects TYPEP more than
most potentially optimizable things in the language.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<·················@nyc.rr.com>...
> But in the recent benchmarking of defun vs defmethod i threw in a
> version doing type and that came out faster than the method. I guess
> that makes it clear I have something wrong, but I thought I'd check in
> here for a confirm.
>
Which is faster depends on so many factors that I couldn't list them
here if I tried: the only way to know is to benchmark (and be prepared
to revise any decision based on the answer when you change any of the
many factors...)
--tim