Every time I use a symbol, which happens a few times per
line, I have doubts about whether I'm triggering a O(log(N))
operation of symbol lookup/internment, where N is the number
of symbols already in use. Will tracing INTERN pinpoint *all*
such non-trivial operations involving symbols?
Don't tell me to read a book about Lisp internals please.
I just don't have the time.
In article <········································@ziplip.com>,
·······@ziplip.com <·······@ziplip.com> wrote:
>Every time I use a symbol, which happens a few times per
>line, I have doubts about whether I'm triggering a O(log(N))
>operation of symbol lookup/internment, where N is the number
>of symbols already in use. Will tracing INTERN pinpoint *all*
>such non-trivial operations involving symbols?
Unless you call INTERN or FIND-SYMBOL explicitly, the overhead only occurs
once, when the file is being loaded. Once the file is loaded, the symbols
are usually represented internally using pointers.
Symbols used to name local variables don't even have to do that if the
function is compiled; the compiler turns these into direct references to a
stack frame or closure offset.
Also, even when INTERN has to be done, it's not likely to be log(N)
difficulty. Packages are almost always implemented as hash tables.
--
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
·······@ziplip.com wrote:
> Every time I use a symbol, which happens a few times per
> line, I have doubts about whether I'm triggering a O(log(N))
> operation of symbol lookup/internment, where N is the number
> of symbols already in use. Will tracing INTERN pinpoint *all*
> such non-trivial operations involving symbols?
symbols are first class objects, ie, comparing two symbols is a direct
comparison. you can even use EQ>
>
> Don't tell me to read a book about Lisp internals please.
> I just don't have the time.
go fuck yourself.
:)
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Career highlights? I had two. I got an intentional walk from
Sandy Koufax and I got out of a rundown against the Mets."
-- Bob Uecker
········@ziplip.com" <·······@ziplip.com> wrote in message news:<········································@ziplip.com>...
> Every time I use a symbol, which happens a few times per
> line, I have doubts about whether I'm triggering a O(log(N))
> operation of symbol lookup/internment, where N is the number
> of symbols already in use. Will tracing INTERN pinpoint *all*
> such non-trivial operations involving symbols?
Symbols are objects, not strings. Their printed representation is
based on their names; when the Lisp compiler or interpreter reads your
source code, it converts these names to objects. That's what interning
is.
The interpretation or compilation of your program takes place over the
resulting data structure; the interning operation is not repeated each
time some section of code is re-evaluated.
A package does not keep symbols in any particular order (such as
lexicographic by name). So there is no reason to use a n-ary
partitioning data structure with logarithmic behavior; more likely,
hashing is used to associate the name strings with objects. Common
Lisp already exposes hash table functions to the user, so there is
little reason not to use them internally as well. But this is only
educated guesswork; each implementation does whatever it does.
You might be concerned about the performance of interning if you are
reading a huge amount of data containing a huge number of distinct
symbols. It's not really a concern when the input data is the source
code of your Lisp application.
········@ziplip.com" <·······@ziplip.com> writes:
> Every time I use a symbol, which happens a few times per line, I
> have doubts about whether I'm triggering a O(log(N)) operation of
> symbol lookup/internment, where N is the number of symbols already
> in use. Will tracing INTERN pinpoint *all* such non-trivial
> operations involving symbols?
In practice, O(log(N)) is just as good as O(1). The logarithm
function grows just as slowly as the exponentional function grows
quickly, if you know what I mean ;-) If I understand you correctly,
you're worrying about the cost of looking up symbols when you
READ-FROM-STRING or something, is that right? Don't. READ is so slow
that lookup cost vanishes in comparison. Or do you mean that you're
using code like
(find 'foo some-list)
? In that case, the address of the symbol FOO is probably hard-coded
into the compiled machine code, so the lookup cost is O(0).
> Don't tell me to read a book about Lisp internals please. I just
> don't have the time.
That's too bad.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
········@ziplip.com" <·······@ziplip.com> writes:
> Every time I use a symbol, which happens a few times per
> line, I have doubts about whether I'm triggering a O(log(N))
> operation of symbol lookup/internment, where N is the number
> of symbols already in use. Will tracing INTERN pinpoint *all*
> such non-trivial operations involving symbols?
>
> Don't tell me to read a book about Lisp internals please.
> I just don't have the time.
You can look up information like this in O(log(N)) time.
I'd give a more detailed answer, but I don't have the time, either.