[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Current master non-deterministic
From: |
David Kastrup |
Subject: |
Re: Current master non-deterministic |
Date: |
Sun, 16 Sep 2012 07:37:56 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.2.50 (gnu/linux) |
Joe Neeman <address@hidden> writes:
> On Sat, Sep 15, 2012 at 2:25 AM, <address@hidden> wrote:
>
>> I realize that LilyPond may be using containers that do not guarantee
>> the order of things (i.e. sets) and that the test I've written may
>> not be a good reflection of what "deterministic" should mean.
>> However, for debugging purposes, I think it's important that when
>> LilyPond compiles the same score, the extents measured and the order
>> in which they're measured remain constant. Otherwise, finding
>> changes in extents, offsets, and skylines is difficult.
>>
>> I think it's important to get 2-3 people brainstorming to figure out
>> where and why this is happening.
>>
>
> There are some places where we sort by pointer (for example, in
> Grob_array::remove_duplicates).
It would appear that the main application is the removal of duplicates,
with the idiom
sort
uniq
in some form or other. This can be replaced by
make map/hash of pointers
iterate through list
if pointer in hash, delete list element, else put pointer in hash
in order to a "stable" O(n lg n) uniq for which the structure of the
final list does not depend on the memory order of the original elements.
However, it requires extra memory along with allocation/deallocation.
--
David Kastrup