Standardspråket för att beskriva algoritmernas aymptotiska beteende är teoretisk beräkningskomplexitet. Vi föreslår en metod för att beskriva programmens asymptotiska beteende i praktiken genom att mäta deras empiriska beräkningskomplexitet. Vår metod innebär att köra ett program om arbetsbelastningar som spänner över flera storleksordningar, mäta deras prestanda, och anpassa dessa observationer till en modell som förutsäger prestanda som en funktion av arbetsbelastning storlek. Jämföra dessa modeller med programmerarens förväntningar eller teoretiska asymptotiska gränser kan avslöja prestanda buggar eller bekräfta att ett programs prestanda skalor som förväntat. Gruppering och ranking program platser baserat på dessa modeller fokuserar uppmärksamheten på skalbarhet-kritisk kod. Vi beskriver vårt verktyg, Trend Profiler (trend-prof), för att konstruera modeller av empirisk beräknings komplexitet som förutsäger hur många gånger varje grundläggande block i ett program körs som en linjär (y = a + bx) eller en powerlaw (y = ax b ) funktion av användarspecificerade funktioner i programmets arbetsbelastning. Vi körde trendproffs på flera stora program och rapportera fall där ett program skalas som förväntat, slå dess värsta fall teoretiska komplexitet bunden, eller hade en prestanda bugg.
Goldsmith, Aiken, och Wilkerson REF föreslår också att köra ett program om arbetsbelastningar av olika storlekar, att mäta prestanda av sina rutiner, och så småningom att passa dessa observationer till en modell som förutspår hur prestanda skalor.
Measuring empirical computational complexity
{'venue': "ESEC-FSE '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}