X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fbreak-substitution.cc;h=e41b09c553a775277ce0858665d79f9184a24211;hb=32b02b2642bd132a548afc163c28667aff074829;hp=4f560e85cd1c2b286b8e9106a0fc31e2a2442cb7;hpb=4a9cacbac6985b76ab22a683ecb0cafc1491e3e0;p=lilypond.git diff --git a/lily/break-substitution.cc b/lily/break-substitution.cc index 4f560e85cd..e41b09c553 100644 --- a/lily/break-substitution.cc +++ b/lily/break-substitution.cc @@ -1,9 +1,10 @@ -#include "grob.hh" +#include +#include + #include "item.hh" -#include "spanner.hh" -#include "system.hh" +#include "system.hh" -static SCM break_criterion; +static SCM break_criterion; void set_break_subsititution (SCM criterion) { @@ -11,14 +12,14 @@ set_break_subsititution (SCM criterion) } /* - Perform the substitution for a single grob. - */ + Perform the substitution for a single grob. +*/ SCM substitute_grob (Grob *sc) { - if (SCM_INUMP (break_criterion)) + if (scm_is_integer (break_criterion)) { - Item * i = dynamic_cast (sc); + Item *i = dynamic_cast (sc); Direction d = to_dir (break_criterion); if (i && i->break_status_dir () != d) { @@ -28,21 +29,20 @@ substitute_grob (Grob *sc) } else { - System * line - = dynamic_cast (unsmob_grob (break_criterion)); - if (sc->line_l () != line) + System *line + = dynamic_cast (unsmob_grob (break_criterion)); + if (sc->get_system () != line) { sc = sc->find_broken_piece (line); - } - - /* now: !sc || (sc && sc->line_l () == line) */ + + /* now: !sc || (sc && sc->get_system () == line) */ if (!sc) return SCM_UNDEFINED; - /* now: sc && sc->line_l () == line */ + /* now: sc && sc->get_system () == line */ if (!line) - return sc->self_scm(); + return sc->self_scm (); /* We don't return SCM_UNDEFINED for @@ -52,17 +52,8 @@ substitute_grob (Grob *sc) - it forces us to mark the parents of a grob, leading to a huge recursion in the GC routine. - */ - - /* - This was introduced in 1.3.49 as a measure to prevent - programming errors. It looks rather expensive (?). - - TODO: - - benchmark , document when (what kind of programming - errors) this happens. */ + if (sc->common_refpoint (line, X_AXIS) && sc->common_refpoint (line, Y_AXIS)) { @@ -71,54 +62,60 @@ substitute_grob (Grob *sc) return SCM_UNDEFINED; } - return sc->self_scm(); + return sc->self_scm (); } - - /* - Do break substitution in S, using CRITERION. Return new value. - CRITERION is either a SMOB pointer to the desired line, or a number - representing the break direction. Do not modify SRC. + Do break substitution in S, using CRITERION. Return new value. + CRITERION is either a SMOB pointer to the desired line, or a number + representing the break direction. Do not modify SRC. - It is rather tightly coded, since it takes a lot of time; it is - one of the top functions in the profile. + It is rather tightly coded, since it takes a lot of time; it is + one of the top functions in the profile. - We don't pass break_criterion as a parameter, since it is - `constant', but takes up stack space. - - It would be nice if we could do this in-place partially. We now - generate a lot of garbage. - */ + We don't pass break_criterion as a parameter, since it is + `constant', but takes up stack space. + It would be nice if we could do this in-place partially. We now + generate a lot of garbage. +*/ SCM do_break_substitution (SCM src) { again: - + if (unsmob_grob (src)) + return substitute_grob (unsmob_grob (src)); + else if (scm_is_vector (src)) { - return substitute_grob (unsmob_grob (src)); + int len = scm_c_vector_length (src); + SCM nv = scm_c_make_vector (len, SCM_UNDEFINED); + for (int i = 0; i < len; i++) + { + SCM si = scm_int2num (i); + scm_vector_set_x (nv, si, + do_break_substitution (scm_vector_ref (src, si))); + } } - else if (ly_pair_p (src)) + else if (scm_is_pair (src)) { /* UGH! breaks on circular lists. */ - SCM newcar = do_break_substitution (ly_car (src)); - SCM oldcdr = ly_cdr (src); - + SCM newcar = do_break_substitution (scm_car (src)); + SCM oldcdr = scm_cdr (src); + if (newcar == SCM_UNDEFINED - && (gh_pair_p (oldcdr) || oldcdr == SCM_EOL)) + && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL)) { /* - This is tail-recursion, ie. - + This is tail-recursion, ie. + return do_break_substution (cdr); We don't want to rely on the compiler to do this. Without tail-recursion, this easily crashes with a stack overflow. */ - src = oldcdr; + src = oldcdr; goto again; } @@ -130,58 +127,333 @@ do_break_substitution (SCM src) return src; } - /* Perform substitution on GROB_LIST using a constant amount of stack. - */ +*/ SCM substitute_grob_list (SCM grob_list) { SCM l = SCM_EOL; - SCM * tail = &l; + SCM *tail = &l; - for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s)) + for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s)) { - SCM n= substitute_grob (unsmob_grob (gh_car (s))); + SCM n = substitute_grob (unsmob_grob (scm_car (s))); if (n != SCM_UNDEFINED) { - *tail = gh_cons (n, SCM_EOL); - tail = SCM_CDRLOC(*tail); + *tail = scm_cons (n, SCM_EOL); + tail = SCM_CDRLOC (*tail); } } 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.is_empty ()) + { + /* + 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 10 grobs.) + */ + + if (len < 300) + return false; + + /* + TODO : should not free it some time? + */ + static Substitution_entry *vec; + static int vec_room; + + if (vec_room < len) + { + vec = (Substitution_entry *) 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; scm_is_pair (s); s = scm_cdr (s)) + { + Grob *g = unsmob_grob (scm_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); + } + } + + /* + sorting vec[sp_index.. len] + is a waste of time -- the staff-spanners screw up the + ordering, since they go across the entire score. + */ + for (int i = sp_indices.size (); i--;) + sp_indices[i] = Slice (sp_index, len - 1); + + 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 + + /* + see below. + */ + if (sym == ly_symbol2scm ("all-elements")) + sc->mutable_property_alist_ + = scm_assq_remove_x (sc->mutable_property_alist_, + ly_symbol2scm ("all-elements")); -SCM grob_list_p; + sc->mutable_property_alist_ = scm_acons (sym, newval, + sc->mutable_property_alist_); + } + + return true; +} /* Although the substitution can be written as - mutable_property_alist_ = do_substitution (mutable_property_alist_), + property_alist = do_substitution (other_property_alist), we have a special function here: we want to invoke a special function for lists of grobs. These can be very long for large - orchestral scores (eg. 1M elements). do_break_substitution() can + orchestral scores (eg. 1M elements). do_break_substitution () can recurse many levels, taking lots of stack space. This becomes a problem if lily is linked against guile with pthreads. pthreads impose small limits on the stack size. - */ +*/ SCM -substitute_mutable_properties (SCM alist) +substitute_mutable_property_alist (SCM alist) { - if (!grob_list_p) - grob_list_p = scm_c_eval_string ("grob-list?"); + SCM grob_list_p = ly_lily_module_constant ("grob-list?"); SCM l = SCM_EOL; SCM *tail = &l; - for (SCM s = alist; gh_pair_p (s); s = gh_cdr (s)) + for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s)) { - SCM sym = gh_caar(s); - SCM val = gh_cdar(s); + SCM sym = scm_caar (s); + SCM val = scm_cdar (s); SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?")); if (type == grob_list_p) @@ -189,9 +461,61 @@ substitute_mutable_properties (SCM alist) else val = do_break_substitution (val); - *tail = gh_cons (gh_cons (sym, val), SCM_EOL); - tail = SCM_CDRLOC (*tail); + if (val != SCM_UNDEFINED) + { + /* + for ly:grob? properties, SCM_UNDEFINED could leak out + through ly:grob-property + */ + *tail = scm_cons (scm_cons (sym, val), SCM_EOL); + tail = SCM_CDRLOC (*tail); + } } - return l; } + +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; + SCM grob_list_p = ly_lily_module_constant ("grob-list?"); + 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); + + /* + For the substitution of a single property, we tack the result onto + mutable_property_alist_ ; mutable_property_alist_ is empty after + Grob::Grob (Grob const&), except that System has all-elements set, + as a side product of typeset_grob () on newly copied spanners. + + Here we clear that list explicitly to free some memory and + counter some of the confusion I encountered while debugging + another problem + + (hwn 4/2/04) + */ + if (sym == ly_symbol2scm ("all-elements")) + sc->mutable_property_alist_ + = scm_assq_remove_x (sc->mutable_property_alist_, + ly_symbol2scm ("all-elements")); + + sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval), + sc->mutable_property_alist_); + } +} +