Re: skyline vertical spacing

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
>> I'm not (yet) convinced that it's worth the effort. It seems that
>> querying at a point is the only thing that gets improved speed.
>> Merging and distance are still O(sum of length of skylines) because we
>> need to at least look at every point in every skyline. Building a
>> skyline is still O(n log n).
> 
> I think you can do better on merging and distance, if you also store
> min/max heights in nodes; with that you could skip looking at an entire
> branch of points. However, you're right in that it is premature to
> optimize this.

Hi,

I have added scripts for profiling, see buildscripts/build-profile.sh.

It turns out that the skyline related routines have replaced 
Grob::get_property() as the top-contender in the profile.  Can you 
have a look to see if this can be  optimized? 


Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 16.39      6.36     6.36 10977483     0.00     0.00  
Building::conceals_beginning(Building const&) const
 16.37     12.72     6.36   666756     0.01     0.01  
common_refpoint_of_array(std::vector<Grob*, std::allocator<Grob*> > const&, 
Grob*, Axis)
  6.21     15.13     2.41  1757179     0.00     0.01  
Skyline::internal_merge_skyline(std::list<Building, std::allocator<Building> 
>*, std::list<Building, std::allocator<Building> >*, std::list<Building, 
std::allocator<Building> >*)
  5.69     17.34     2.21 18440608     0.00     0.00  
skyline_trailing_part(std::list<Building, std::allocator<Building> >*, double)
  5.62     19.52     2.18 15397616     0.00     0.00  
Building::conceals(Building const&) const
  4.05     21.09     1.57  6362790     0.00     0.00  Building::precompute()
  3.79     22.56     1.47  1694853     0.00     0.00  
Page_spacer::calc_subproblem(unsigned int, unsigned int)
  1.21     23.03     0.47 27360933     0.00     0.00  
Interval_t<double>::length() const
  1.20     23.49     0.47  5219812     0.00     0.00  Grob::extent(Grob*, Axis) 
const
  1.13     23.93     0.44 26448697     0.00     0.00  
Grob::internal_get_property_data(scm_unused_struct*) const
  0.84     24.26     0.33 20164826     0.00     0.00  Grob::get_offset(Axis) 
const


-- 

Han-Wen Nienhuys - address@hidden - http://www.xs4all.nl/~hanwen

LilyPond Software Design
 -- Code for Music Notation
http://www.lilypond-design.com