From aac814e0904dde5c2d5bba5f165e61826c72b1aa Mon Sep 17 00:00:00 2001 From: Han-Wen Nienhuys Date: Sat, 17 Aug 2002 15:30:23 +0000 Subject: [PATCH] * lily/system.cc (spanner_count): new function * lily/break-substitution.cc (fast_fubstitute_grob_list): special function for break substitutions on groblists in spanners. By reordering the elements of the list, we can skip large parts of the list in the break substitution. This brings the complexity of Lily back to more-or-less linear in the length of the score. --- ChangeLog | 17 +- lily/axis-group-interface.cc | 5 +- lily/break-substitution.cc | 323 +++++++++++++++++++++++++++++++++++ lily/grob-property.cc | 91 +--------- lily/grob.cc | 20 +-- lily/include/grob.hh | 5 +- lily/include/item.hh | 1 - lily/include/spanner.hh | 9 +- lily/include/system.hh | 2 + lily/paper-score.cc | 4 +- lily/spanner.cc | 4 + lily/system.cc | 16 ++ 12 files changed, 384 insertions(+), 113 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4e948b5c38..b422dcb87a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,10 +1,21 @@ 2002-08-17 Han-Wen Nienhuys - * lily/source-file.cc (init_port): add an SCM port to the - sourcefile as well. + * lily/system.cc (spanner_count): new function + + * lily/break-substitution.cc (fast_fubstitute_grob_list): special + function for break substitutions on groblists in spanners. By + reordering the elements of the list, we can skip large parts of + the list in the break substitution. This brings the complexity of + Lily back to more-or-less linear in the length of the score. + + Measured speed increase: 20 % (coriolan, without -O2) * lily/parse-scm.cc (parse_handler): don't construct a new strport - for every parsing. + for every parsing. This saves a lot of garbage on large files that + have many # constructs. + + * lily/source-file.cc (init_port): add an SCM port to the + sourcefile as well. * lily/include/input-file-results.hh: move from file-results. Rename Input_file_settings to Input_file_results. diff --git a/lily/axis-group-interface.cc b/lily/axis-group-interface.cc index ec4e202303..1efc878a92 100644 --- a/lily/axis-group-interface.cc +++ b/lily/axis-group-interface.cc @@ -58,10 +58,11 @@ Axis_group_interface::group_extent_callback (SCM element_smob, SCM scm_axis) Grob *me = unsmob_grob (element_smob); Axis a = (Axis) gh_scm2int (scm_axis); - Grob * common = common_refpoint_of_list (me->get_grob_property ("elements"), me, a); + SCM elts = me->get_grob_property ("elements"); + Grob * common = common_refpoint_of_list (elts, me, a); Real my_coord = me->relative_coordinate (common, a); - Interval r (relative_group_extent (a, common, me->get_grob_property ("elements"))); + Interval r (relative_group_extent (a, common,elts)); return ly_interval2scm (r - my_coord); } diff --git a/lily/break-substitution.cc b/lily/break-substitution.cc index 78a90b9519..31a887e20c 100644 --- a/lily/break-substitution.cc +++ b/lily/break-substitution.cc @@ -1,3 +1,5 @@ +#include + #include "grob.hh" #include "item.hh" #include "spanner.hh" @@ -164,6 +166,300 @@ substitute_grob_list (SCM grob_list) return l; } +/* + We don't do + + forall b in broken-childs: + forall p in properties: + forall g in p (if grob-list): + g := substitute (g) + + for spanners since this is O(SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT = + O(GROBCOUNT), we have a quadratic algorithm. --for a single spanner + + This is problematic: with large (long) scores, the costs can be + significant; especially all-elements in System, can become huge. For + a typical 50 page score, it requires running through a 100k list 50 + times. + + Instead: + + forall p in properties: + (if grob list) + + put grob list in array, + + reorder array so spanners are separate -- O(grobcount) + + find first and last indexes of grobs on a specific system + + for items this is O(itemcount) + + for spanners this is O(sum-of spanner-system-ranges) + + perform the substitution O(sum-of spanner-system-ranges) + + + The complexity is harder to determine, but should be subquadratic; + + For the situation above, we run through the entire 100k list once, + and also (more or less) once through the item part of the 100k (say + 98k elements) of the list. + + +These timings were measured without -O2. + + lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %. + + coriolan, before 2:30, after: 1:59. Increase of 20%. + + moz-k498-p1, before 24.10, after: 19.790s, Increase of 18% + + +*/ + + +Slice +spanner_system_range (Spanner* sp) +{ + Slice rv; + + if (System*st = sp->get_system()) + { + rv = Slice (st->rank_, st->rank_); + } + else + { + if (sp->broken_intos_.size()) + rv = Slice (sp->broken_intos_[0]->get_system()->rank_, + sp->broken_intos_.top()->get_system()->rank_); + } + return rv; +} + +Slice +item_system_range (Item* it) +{ + if (System*st= it->get_system()) + return Slice (st->rank_, st->rank_); + + Slice sr; + Direction d = LEFT; + do + { + Item *bi = it->find_prebroken_piece (d); + if (bi && bi->get_system()) + sr.add_point (bi->get_system()->rank_); + } + while (flip(&d)!=LEFT); + + return sr; +} + +Slice +grob_system_range (Grob *g) +{ + if (Spanner*s = dynamic_cast(g)) + return spanner_system_range (s); + else if (Item* it = dynamic_cast (g)) + return item_system_range (it); + else + return Slice(); +} + + + +struct Substitution_entry +{ + Grob * grob_; + short left_; + short right_; + + void set (Grob*g, Slice sr) + { + grob_ = g; + /* + duh, don't support scores with more than 32000 systems. + */ + if (sr.empty_b()) + { + /* + overflow if we don't treat this specially. + */ + left_ = 1; + right_ = -1; + } + else + { + left_ = sr[LEFT]; + right_ = sr[RIGHT]; + } + } + Substitution_entry() + { + grob_ =0; + left_ = right_ = -2; + } + + int length () { return right_ - left_ ; } + static int + item_compare (void const * a , void const * b) + { + return ((Substitution_entry*)a)->left_ - + ((Substitution_entry*)b)->left_; + } + + static int + spanner_compare (void const * a , void const * b) + { + return ((Substitution_entry*)a)->length() - + ((Substitution_entry*)b)->length (); + } +}; + + + +bool +Spanner::fast_fubstitute_grob_list (SCM sym, + SCM grob_list) +{ + int len = scm_ilength (grob_list); + + /* + Only do this complicated thing for large lists. This has the added + advantage that we won't screw up the ordering for elements in + alignments (which typically don't have more than 100 grobs.) + */ + + if (len < 100) + return false; + + + /* + TODO : should not reallocate every time? + */ + static Substitution_entry * vec; + static int vec_room; + + if (vec_room < len) + { + vec = (Substitution_entry*) scm_realloc (vec, sizeof (Substitution_entry) * len); + vec_room = len; + } + + Slice system_range = spanner_system_range (this); + + Array it_indices; + Array sp_indices; + for (int i = 0; i <= system_range.length (); i++) + { + it_indices.push (Slice (len, 0)); + sp_indices.push (Slice (len, 0)); + } + + + int sp_index = len; + int it_index = 0; + for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s)) + { + Grob * g = unsmob_grob (gh_car(s)); + + Slice sr = grob_system_range (g); + sr.intersect (system_range); + + int idx = 0; + if (dynamic_cast(g)) + { + idx =--sp_index; + } + else if (dynamic_cast (g)) + { + idx = it_index++; + } + + vec[idx].set (g, sr); + } + + qsort (vec, it_index, + sizeof (Substitution_entry), &Substitution_entry::item_compare); + + Array *arrs[] = { + &it_indices, &sp_indices + }; + + for (int i = 0; i < it_index ;i++) + { + for (int j = vec[i].left_; j <= vec[i].right_; j++) + { + it_indices[j - system_range[LEFT]].add_point (i); + } + } + +#if 0 + qsort (vec + sp_index, len - sp_index, + sizeof (Substitution_entry), &Substitution_entry::spanner_compare); + /* + This is a waste of time -- the staff-spanners screw up the + ordering, since they go across the entire score. + */ + for (int i = sp_index; i < len ;i++) + { + + for (int j = vec[i].left_; j <= vec[i].right_; j++) + { + sp_indices[j - system_range[LEFT]].add_point (i); + } + } +#else + for (int i = sp_indices.size(); i--;) + sp_indices[i]= Slice (sp_index, len-1); +#endif + + + assert (it_index <= sp_index); + + assert (broken_intos_.size () == system_range.length () + 1); + for (int i = 0; i < broken_intos_.size(); i++) + { + Grob * sc = broken_intos_[i]; + System * l = sc->get_system (); + set_break_subsititution (l ? l->self_scm(): SCM_UNDEFINED); + + SCM newval = SCM_EOL; + SCM * tail = &newval; + + for (int k = 0; k < 2;k++) + for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++) + { + SCM subs =substitute_grob (vec[j].grob_); + if (subs!= SCM_UNDEFINED) + { + *tail = scm_cons (subs, SCM_EOL); + + tail = SCM_CDRLOC(*tail); + } + + } + +#ifdef PARANOIA + + printf ("%d (%d), sp %d (%d)\n", + it_indices [i].length (), it_index, + sp_indices[i].length() , len -sp_index); + + { + SCM l1 =substitute_grob_list (grob_list); + assert (scm_ilength (l1) == scm_ilength (newval)); + } +#endif + + sc->mutable_property_alist_ = scm_acons (sym, newval, + sc->mutable_property_alist_); + } + + return true; +} + SCM grob_list_p; @@ -207,3 +503,30 @@ substitute_mutable_property_alist (SCM alist) } +void +Spanner::substitute_one_mutable_property (SCM sym, + SCM val) +{ + SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?")); + Spanner*s = this; + + bool fast_done = false; + if (type == grob_list_p) + fast_done = s->fast_fubstitute_grob_list (sym, val); + + if (!fast_done) + for (int i = 0; i < s->broken_intos_ .size (); i++) + { + Grob * sc = s->broken_intos_[i]; + System * l = sc->get_system (); + set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED); + + SCM newval = (type == grob_list_p) + ? substitute_grob_list (val) + : do_break_substitution(val); + + sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval), + sc->mutable_property_alist_); + } +} + diff --git a/lily/grob-property.cc b/lily/grob-property.cc index d7158d6df5..2ea216668a 100644 --- a/lily/grob-property.cc +++ b/lily/grob-property.cc @@ -19,66 +19,15 @@ #include "misc.hh" #include "item.hh" -/* - HASHING_FOR_MUTABLE_PROPS: - - - plain, -O0 compile - -user 0m12.400s - -sz == 13, -O0 compile - - xdvi trip - -user 0m13.780s - -sz == 5 - - -user 0m13.000s - -sz == 3 - - -user 0m13.080s - -Hashing doesn't improve the result of grob property lookup, at least -not with naive hashing. It is possible that the overhead of the -scm_hash* functions take too much time. One way to solve this is by -using vector accesses directly, and precompute the hashvalues, similar -to CACHE_SYMBOLS. That option could only cause slowdowns if the hash -tables produces weird cache-line trashing. - -Second option: we could index immutable props in a hash tab as -well. This only takes space, since they are immutable no updates are -needed. This does take a lot of space, since we must duplicate the -alists (but not the entries). - -*/ -// #define HASHING_FOR_MUTABLE_PROPS SCM Grob::get_property_alist_chain (SCM def) const { -#ifndef HASHING_FOR_MUTABLE_PROPS return scm_list_n (mutable_property_alist_, immutable_property_alist_, def, SCM_UNDEFINED); -#else - SCM chain = gh_list (immutable_property_alist_, def, SCM_UNDEFINED); - SCM * velts = SCM_VELTS (mutable_property_alist_); - int l = SCM_VECTOR_LENGTH(mutable_property_alist_); - for (int i = 0; i < l; i++) - { - if (gh_pair_p (velts[i])) - chain = gh_cons ( velts[i], chain); - } - - return chain; -#endif } @@ -94,12 +43,9 @@ void Grob::add_to_list_property (SCM sym, SCM thing) { SCM handle -#ifndef HASHING_FOR_MUTABLE_PROPS = scm_sloppy_assq (sym, mutable_property_alist_) -#else - = scm_hashq_get_handle (mutable_property_alist_, sym); -#endif ; + if (handle != SCM_BOOL_F) { gh_set_cdr_x (handle, gh_cons (thing, gh_cdr (handle))); @@ -113,12 +59,9 @@ Grob::add_to_list_property (SCM sym, SCM thing) handle = scm_sloppy_assq (sym, immutable_property_alist_); SCM tail = (handle != SCM_BOOL_F) ? gh_cdr(handle) : SCM_EOL; SCM val = gh_cons (thing, tail); -#ifndef HASHING_FOR_MUTABLE_PROPS + mutable_property_alist_ = gh_cons (gh_cons (sym, val), mutable_property_alist_); -#else - scm_hashq_set_x (mutable_property_alist_, sym, val); -#endif } } @@ -142,29 +85,16 @@ Grob::internal_set_grob_property (SCM s, SCM v) } #endif -#ifndef HASHING_FOR_MUTABLE_PROPS mutable_property_alist_ = scm_assq_set_x (mutable_property_alist_, s, v); -#else - scm_hashq_set_x (mutable_property_alist_, s, v); -#endif } SCM Grob::internal_get_grob_property (SCM sym) const { -#ifndef HASHING_FOR_MUTABLE_PROPS SCM s = scm_sloppy_assq (sym, mutable_property_alist_); if (s != SCM_BOOL_F) return ly_cdr (s); -#else - if (mutable_property_alist_ == SCM_EOL) - return SCM_EOL; - - SCM s = scm_hashq_ref (mutable_property_alist_, sym, SCM_EOL); - if (s!=SCM_EOL) - return s; -#endif s = scm_sloppy_assq (sym, immutable_property_alist_); @@ -183,24 +113,7 @@ void Grob::substitute_mutable_properties (SCM crit, SCM orig) { set_break_subsititution(crit); -#ifndef HASHING_FOR_MUTABLE_PROPS mutable_property_alist_ = substitute_mutable_property_alist (orig); -#else - if (orig == SCM_EOL) - { - mutable_property_alist_ = SCM_EOL; - return ; - } - - SCM * src_elts = SCM_VELTS (orig); - SCM * dest_elts = SCM_VELTS (mutable_property_alist_); - unsigned int l = SCM_VECTOR_LENGTH(mutable_property_alist_); - assert (l == SCM_VECTOR_LENGTH(orig)); - for (unsigned int i = 0; i < l; i++) - { - dest_elts[i] = substitute_mutable_property_alist (src_elts[i]); - } -#endif } diff --git a/lily/grob.cc b/lily/grob.cc index 9c8833f8f3..a30f020c8e 100644 --- a/lily/grob.cc +++ b/lily/grob.cc @@ -320,30 +320,28 @@ Grob::add_dependency (Grob*e) void Grob::handle_broken_dependencies () { - Spanner * s= dynamic_cast (this); - if (original_ && s) + Spanner * sp = dynamic_cast (this); + if (original_ && sp) return; - if (s) + if (sp) { - for (int i = 0; i< s->broken_intos_ .size (); i++) + for (SCM s = mutable_property_alist_; gh_pair_p(s); + s = gh_cdr(s)) { - Grob * sc = s->broken_intos_[i]; - System * l = sc->get_system (); - - sc->substitute_mutable_properties (l ? l->self_scm () : SCM_UNDEFINED, - mutable_property_alist_); + sp->substitute_one_mutable_property (gh_caar (s), + gh_cdar (s)); + } } - System *system = get_system (); if (live () && system && common_refpoint (system, X_AXIS) && common_refpoint (system, Y_AXIS)) { substitute_mutable_properties (system ? system->self_scm () : SCM_UNDEFINED, - mutable_property_alist_); + mutable_property_alist_); } else if (dynamic_cast (this)) { diff --git a/lily/include/grob.hh b/lily/include/grob.hh index ff8308ad14..8f11341b25 100644 --- a/lily/include/grob.hh +++ b/lily/include/grob.hh @@ -37,10 +37,11 @@ typedef void (Grob::*Grob_method_pointer) (void); Basic output object. */ class Grob { -private: +protected: SCM immutable_property_alist_; SCM mutable_property_alist_; - + friend class Spanner; + void substitute_mutable_properties(SCM,SCM); public: Grob *original_; diff --git a/lily/include/item.hh b/lily/include/item.hh index 37eb33f267..58c9969b62 100644 --- a/lily/include/item.hh +++ b/lily/include/item.hh @@ -37,7 +37,6 @@ public: Item *find_prebroken_piece (Direction) const; Grob *find_broken_piece (System *) const; - virtual System *get_system () const; virtual Paper_column *get_column () const; virtual void handle_prebroken_dependencies (); diff --git a/lily/include/spanner.hh b/lily/include/spanner.hh index 1dcc0b3c0e..c146182f17 100644 --- a/lily/include/spanner.hh +++ b/lily/include/spanner.hh @@ -31,15 +31,17 @@ */ class Spanner : public Grob { Drul_array spanned_drul_; - + public: DECLARE_SCHEME_CALLBACK (set_spacing_rods, (SCM)); Link_array broken_intos_; + int break_index_; // todo: move to somewhere else. Real get_broken_left_end_align () const; - + void substitute_one_mutable_property (SCM sym, SCM val) ; + bool fast_fubstitute_grob_list (SCM sym, SCM grob_list); // TODO: make virtual and do this for Items as well. Interval_t spanned_rank_iv (); void set_bound (Direction d, Grob*); @@ -55,15 +57,14 @@ public: virtual Grob* find_broken_piece (System*) const; virtual SCM do_derived_mark (); static bool has_interface (Grob*); + virtual System *get_system () const; protected: void set_my_columns (); VIRTUAL_COPY_CONS (Grob); virtual void do_break_processing (); - virtual System *get_system () const; }; - void add_bound_item (Spanner*, Grob*); ///DECLARE_UNSMOB (Spanner, spanner); diff --git a/lily/include/system.hh b/lily/include/system.hh index 8921eb62f1..670fef96c5 100644 --- a/lily/include/system.hh +++ b/lily/include/system.hh @@ -29,6 +29,8 @@ public: /// is #c# contained in #*this#? bool contains_b (Paper_column const *c) const; int element_count () const; + int spanner_count () const; + void break_into_pieces (Array const&); void output_lines (); diff --git a/lily/paper-score.cc b/lily/paper-score.cc index bf7ce0e0b5..295ba16265 100644 --- a/lily/paper-score.cc +++ b/lily/paper-score.cc @@ -74,7 +74,9 @@ void Paper_score::process () { if (verbose_global_b) - progress_indication (_f ("Element count %d ", system_->element_count ())); + progress_indication (_f ("Element count %d (spanners %d) ", + system_->element_count (), + system_->spanner_count ())); progress_indication (_ ("Preprocessing elements...") + " "); diff --git a/lily/spanner.cc b/lily/spanner.cc index 8e4b060774..b29c40425b 100644 --- a/lily/spanner.cc +++ b/lily/spanner.cc @@ -119,6 +119,8 @@ Spanner::do_break_processing () } } broken_intos_.sort (Spanner::compare); + for (int i= broken_intos_.size();i--;) + broken_intos_[i]->break_index_ = i; } void @@ -149,6 +151,7 @@ Spanner::spanned_rank_iv () return iv; } + Item* Spanner::get_bound (Direction d) const { @@ -196,6 +199,7 @@ Spanner::set_bound (Direction d, Grob*s) Spanner::Spanner (SCM s) : Grob (s) { + break_index_ = 0; spanned_drul_[LEFT]=0; spanned_drul_[RIGHT]=0; Group_interface::add_thing (this, ly_symbol2scm ("interfaces"), ly_symbol2scm ("spanner-interface")); diff --git a/lily/system.cc b/lily/system.cc index f1994d2129..2536331c4c 100644 --- a/lily/system.cc +++ b/lily/system.cc @@ -45,6 +45,22 @@ System::element_count () const return scm_ilength (get_grob_property ("all-elements")); } +int +System::spanner_count () const +{ + int k =0; + for (SCM s = get_grob_property ("all-elements"); + gh_pair_p (s); s = ly_cdr (s)) + { + if (dynamic_cast (unsmob_grob (gh_car(s)))) + k++; + } + + return k; +} + + + void System::typeset_grob (Grob * elem) { -- 2.39.5