obarray confusion

obarray confusion

[Sean McAfee]

(mapatoms (lambda (s) (incf n))) tells me I have 43061 symbols defined.
(length obarray) tells me the standard obarray has a size of 1511.

My understanding is that an obarray is essentially a hash table with
collision chaining.  But this would mean that the linked list of symbols
in each bucket has an average length of 43061 / 1511 ≈ 28.

Emacs's symbol lookup couldn't possibly be that inefficient, could it?

Re: obarray confusion

[David Kastrup]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> Sean McAfee <eefacm@gmail.com> writes:
>
>> (mapatoms (lambda (s) (incf n))) tells me I have 43061 symbols defined.
>> (length obarray) tells me the standard obarray has a size of 1511.
>>
>> My understanding is that an obarray is essentially a hash table with
>> collision chaining.  But this would mean that the linked list of symbols
>> in each bucket has an average length of 43061 / 1511 ≈ 28.
>>
>> Emacs's symbol lookup couldn't possibly be that inefficient, could it?
>
> Symbols are interned only when they are read, which doesn't occur often.

28 is quite the bucket size.  If the average bucket size is larger than
1 for the dumped Emacs already, that's just a case of bad defaults, and
of course it should affect byte compilation times quite a bit.

-- 
David Kastrup

Re: obarray confusion

[Pascal J. Bourguignon]

David Kastrup <dak@gnu.org> writes:

> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>
>> Sean McAfee <eefacm@gmail.com> writes:
>>
>>> (mapatoms (lambda (s) (incf n))) tells me I have 43061 symbols defined.
>>> (length obarray) tells me the standard obarray has a size of 1511.
>>>
>>> My understanding is that an obarray is essentially a hash table with
>>> collision chaining.  But this would mean that the linked list of symbols
>>> in each bucket has an average length of 43061 / 1511 ≈ 28.
>>>
>>> Emacs's symbol lookup couldn't possibly be that inefficient, could it?
>>
>> Symbols are interned only when they are read, which doesn't occur often.
>
> 28 is quite the bucket size.  If the average bucket size is larger than
> 1 for the dumped Emacs already, that's just a case of bad defaults, and
> of course it should affect byte compilation times quite a bit.

Obviously, emacs is optimized for editing, not for compiling ;-)

I agree that the size of the obarray should adapt to its content.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

Re: obarray confusion

[Stefan Monnier]

> (mapatoms (lambda (s) (incf n))) tells me I have 43061 symbols defined.
> (length obarray) tells me the standard obarray has a size of 1511.

> My understanding is that an obarray is essentially a hash table with
> collision chaining.  But this would mean that the linked list of symbols
> in each bucket has an average length of 43061 / 1511 ≈ 28.

That's right.

> Emacs's symbol lookup couldn't possibly be that inefficient, could it?

I think it not only could.


        Stefan