incremental scaling

[Mark Dufour]

hi all,

here's a graph of the current analysis time versus program size (sloccount), for most of the examples plus one large new example that I can't share yet. the one on the right is the new c64 emulator example. two examples are left out, because they end with the maximum number of iterations, because of some interminable loop they end up in (though the results are already correct at that point, and the non-termination problem will probably go away at some point).

who said type inference doesn't scale..? ;-)


thanks,
mark.
--
http://www.youtube.com/watch?v=E6LsfnBmdnk

[Jérémie Roquet]

Hi,

2010/10/19 Mark Dufour <mark....@gmail.com>:

> here's a graph of the current analysis time versus program size (sloccount),
> for most of the examples plus one large new example that I can't share yet.
> the one on the right is the new c64 emulator example. two examples are left
> out, because they end with the maximum number of iterations, because of some
> interminable loop they end up in (though the results are already correct at
> that point, and the non-termination problem will probably go away at some
> point).
>
> who said type inference doesn't scale..? ;-)

Is it linear? Wow :)

Is it also the case from a theorical point of view?

Best regards,

--
Jérémie

[Mark Dufour]

hi jeremie,

> who said type inference doesn't scale..? ;-)

Is it linear? Wow :)

Is it also the case from a theorical point of view?

theoretically, I'd expect it being O(N**2), since an incremental analysis means we're essentially analyzing the program O(N) times. a quadratic regression line supports this, by ever so slighly curving up.. :) a possible explanation for the second order coefficient being so small is that the analysis is able to disregard large parts of the code while 'solving' the 5 newly added functions each increment.

in any case, it would be nice to have some more datapoints on the right.. :-)

thanks!

mark.
--
http://www.youtube.com/watch?v=E6LsfnBmdnk

[Mark Dufour]

btw, following the quadratic regression line, it would take around 2 hours on my CPU (Q9550) to analyze a 10,000 line program (sloccount). that's fast enough for me to worry more about other issues than scalability.. I'm sure it can still be much improved, but the added complexity does not seem worth it at the moment. I'd like to see an actual 10,000 line program compile at least once first.. :-)

[srepmub]

btw, the example at around 1,000 lines is obviously the new raytracer.