9 static SCM break_criterion;
11 set_break_subsititution (SCM criterion)
13 break_criterion = criterion;
17 Perform the substitution for a single grob.
20 substitute_grob (Grob *sc)
22 if (SCM_INUMP (break_criterion))
24 Item * i = dynamic_cast<Item*> (sc);
25 Direction d = to_dir (break_criterion);
26 if (i && i->break_status_dir () != d)
28 Item *br = i->find_prebroken_piece (d);
29 return (br) ? br->self_scm () : SCM_UNDEFINED;
35 = dynamic_cast<System*> (unsmob_grob (break_criterion));
36 if (sc->get_system () != line)
38 sc = sc->find_broken_piece (line);
42 /* now: !sc || (sc && sc->get_system () == line) */
46 /* now: sc && sc->get_system () == line */
48 return sc->self_scm();
51 We don't return SCM_UNDEFINED for
52 suicided grobs, for two reasons
54 - it doesn't work (strange disappearing objects)
56 - it forces us to mark the parents of a grob, leading to
57 a huge recursion in the GC routine.
60 if (sc->common_refpoint (line, X_AXIS)
61 && sc->common_refpoint (line, Y_AXIS))
63 return sc->self_scm ();
68 return sc->self_scm();
74 Do break substitution in S, using CRITERION. Return new value.
75 CRITERION is either a SMOB pointer to the desired line, or a number
76 representing the break direction. Do not modify SRC.
78 It is rather tightly coded, since it takes a lot of time; it is
79 one of the top functions in the profile.
81 We don't pass break_criterion as a parameter, since it is
82 `constant', but takes up stack space.
84 It would be nice if we could do this in-place partially. We now
85 generate a lot of garbage.
88 do_break_substitution (SCM src)
92 if (unsmob_grob (src))
94 return substitute_grob (unsmob_grob (src));
96 else if (gh_vector_p (src))
98 int l = SCM_VECTOR_LENGTH (src);
99 SCM nv = scm_c_make_vector (l, SCM_UNDEFINED);
101 for (int i =0 ; i< l ; i++)
103 SCM si = scm_int2num (i);
104 scm_vector_set_x (nv, si, do_break_substitution (scm_vector_ref (src, si)));
107 else if (ly_pair_p (src))
110 UGH! breaks on circular lists.
112 SCM newcar = do_break_substitution (ly_car (src));
113 SCM oldcdr = ly_cdr (src);
115 if (newcar == SCM_UNDEFINED
116 && (gh_pair_p (oldcdr) || oldcdr == SCM_EOL))
119 This is tail-recursion, ie.
121 return do_break_substution (cdr);
123 We don't want to rely on the compiler to do this. Without
124 tail-recursion, this easily crashes with a stack overflow. */
129 return scm_cons (newcar, do_break_substitution (oldcdr));
139 Perform substitution on GROB_LIST using a constant amount of stack.
142 substitute_grob_list (SCM grob_list)
147 for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s))
149 SCM n= substitute_grob (unsmob_grob (gh_car (s)));
151 if (n != SCM_UNDEFINED)
153 *tail = gh_cons (n, SCM_EOL);
154 tail = SCM_CDRLOC(*tail);
164 forall b in broken-childs:
165 forall p in properties:
166 forall g in p (if grob-list):
169 for spanners since this is O(SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
170 O(GROBCOUNT), we have a quadratic algorithm. --for a single spanner
172 This is problematic: with large (long) scores, the costs can be
173 significant; especially all-elements in System, can become huge. For
174 a typical 50 page score, it requires running through a 100k list 50
179 forall p in properties:
182 put grob list in array,
184 reorder array so spanners are separate -- O(grobcount)
186 find first and last indexes of grobs on a specific system
188 for items this is O(itemcount)
190 for spanners this is O(sum-of spanner-system-ranges)
192 perform the substitution O(sum-of spanner-system-ranges)
195 The complexity is harder to determine, but should be subquadratic;
197 For the situation above, we run through the entire 100k list once,
198 and also (more or less) once through the item part of the 100k (say
199 98k elements) of the list.
202 These timings were measured without -O2.
204 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
206 coriolan, before 2:30, after: 1:59. Increase of 20%.
208 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
215 spanner_system_range (Spanner* sp)
219 if (System*st = sp->get_system())
221 rv = Slice (st->rank_, st->rank_);
225 if (sp->broken_intos_.size())
226 rv = Slice (sp->broken_intos_[0]->get_system()->rank_,
227 sp->broken_intos_.top()->get_system()->rank_);
233 item_system_range (Item* it)
235 if (System*st= it->get_system())
236 return Slice (st->rank_, st->rank_);
242 Item *bi = it->find_prebroken_piece (d);
243 if (bi && bi->get_system())
244 sr.add_point (bi->get_system()->rank_);
246 while (flip(&d)!=LEFT);
252 grob_system_range (Grob *g)
254 if (Spanner*s = dynamic_cast<Spanner*>(g))
255 return spanner_system_range (s);
256 else if (Item* it = dynamic_cast<Item*> (g))
257 return item_system_range (it);
264 struct Substitution_entry
270 void set (Grob*g, Slice sr)
274 duh, don't support scores with more than 32000 systems.
279 overflow if we don't treat this specially.
296 int length () { return right_ - left_ ; }
298 item_compare (void const * a , void const * b)
300 return ((Substitution_entry*)a)->left_ -
301 ((Substitution_entry*)b)->left_;
305 spanner_compare (void const * a , void const * b)
307 return ((Substitution_entry*)a)->length() -
308 ((Substitution_entry*)b)->length ();
315 Spanner::fast_fubstitute_grob_list (SCM sym,
318 int len = scm_ilength (grob_list);
321 Only do this complicated thing for large lists. This has the added
322 advantage that we won't screw up the ordering for elements in
323 alignments (which typically don't have more than 10 grobs.)
331 TODO : should not free it some time?
333 static Substitution_entry * vec;
338 vec = (Substitution_entry*) realloc (vec, sizeof (Substitution_entry) * len);
342 Slice system_range = spanner_system_range (this);
344 Array<Slice> it_indices;
345 Array<Slice> sp_indices;
346 for (int i = 0; i <= system_range.length (); i++)
348 it_indices.push (Slice (len, 0));
349 sp_indices.push (Slice (len, 0));
355 for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s))
357 Grob * g = unsmob_grob (gh_car(s));
359 Slice sr = grob_system_range (g);
360 sr.intersect (system_range);
363 if (dynamic_cast<Spanner*>(g))
367 else if (dynamic_cast<Item*> (g))
372 vec[idx].set (g, sr);
375 qsort (vec, it_index,
376 sizeof (Substitution_entry), &Substitution_entry::item_compare);
378 Array<Slice> *arrs[] = {
379 &it_indices, &sp_indices
382 for (int i = 0; i < it_index ;i++)
384 for (int j = vec[i].left_; j <= vec[i].right_; j++)
386 it_indices[j - system_range[LEFT]].add_point (i);
391 sorting vec[sp_index.. len]
392 is a waste of time -- the staff-spanners screw up the
393 ordering, since they go across the entire score.
395 for (int i = sp_indices.size(); i--;)
396 sp_indices[i]= Slice (sp_index, len-1);
399 assert (it_index <= sp_index);
401 assert (broken_intos_.size () == system_range.length () + 1);
402 for (int i = 0; i < broken_intos_.size(); i++)
404 Grob * sc = broken_intos_[i];
405 System * l = sc->get_system ();
406 set_break_subsititution (l ? l->self_scm(): SCM_UNDEFINED);
408 SCM newval = SCM_EOL;
409 SCM * tail = &newval;
411 for (int k = 0; k < 2;k++)
412 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
414 SCM subs =substitute_grob (vec[j].grob_);
415 if (subs!= SCM_UNDEFINED)
417 *tail = scm_cons (subs, SCM_EOL);
419 tail = SCM_CDRLOC(*tail);
426 printf ("%d (%d), sp %d (%d)\n",
427 it_indices [i].length (), it_index,
428 sp_indices[i].length() , len -sp_index);
431 SCM l1 =substitute_grob_list (grob_list);
432 assert (scm_ilength (l1) == scm_ilength (newval));
439 if (sym == ly_symbol2scm ("all-elements"))
440 sc->set_grob_property ("all-elements", SCM_EOL);
442 sc->mutable_property_alist_ = scm_acons (sym, newval,
443 sc->mutable_property_alist_);
453 Although the substitution can be written as
455 property_alist = do_substitution (other_property_alist),
457 we have a special function here: we want to invoke a special
458 function for lists of grobs. These can be very long for large
459 orchestral scores (eg. 1M elements). do_break_substitution() can
460 recurse many levels, taking lots of stack space.
462 This becomes a problem if lily is linked against guile with
463 pthreads. pthreads impose small limits on the stack size.
466 substitute_mutable_property_alist (SCM alist)
469 grob_list_p = scm_c_eval_string ("grob-list?");
473 for (SCM s = alist; gh_pair_p (s); s = gh_cdr (s))
475 SCM sym = gh_caar(s);
476 SCM val = gh_cdar(s);
477 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
479 if (type == grob_list_p)
480 val = substitute_grob_list (val);
482 val = do_break_substitution (val);
484 *tail = gh_cons (gh_cons (sym, val), SCM_EOL);
485 tail = SCM_CDRLOC (*tail);
493 Spanner::substitute_one_mutable_property (SCM sym,
496 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
499 bool fast_done = false;
500 if (type == grob_list_p)
501 fast_done = s->fast_fubstitute_grob_list (sym, val);
504 for (int i = 0; i < s->broken_intos_ .size (); i++)
506 Grob * sc = s->broken_intos_[i];
507 System * l = sc->get_system ();
508 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
510 SCM newval = (type == grob_list_p)
511 ? substitute_grob_list (val)
512 : do_break_substitution (val);
515 For the substitution of a single property, we tack the result onto
516 mutable_property_alist_ ; mutable_property_alist_ is empty after
517 Grob::Grob (Grob const&), except that System has all-elements set,
518 as a side product of typeset_grob() on newly copied spanners.
520 Here we clear that list explicitly to free some memory and
521 counter some of the confusion I encountered while debugging
526 if (sym == ly_symbol2scm ("all-elements"))
527 sc->set_grob_property ("all-elements", SCM_EOL);
529 sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
530 sc->mutable_property_alist_);