bug-lilypond
[Top][All Lists]
Advanced

[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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]