Stickybit

What we do

We provide you with the right services enablling your business operations to function and evolve in accordance with your plan. Your need might involve model driven code generation, performance tuning of ICT systems, secure Cloud deployment or compute clusters. Our toolbox contains the knowledge and skill required to choose, create and establish the technology you need.

We are experienced consultants and we will effectively contribute to your organisation and we're shrewd networkers who knows the value of getting a line to the right people to get tthe job done.

We provide professional services within three areas: ICT Architecture, System's Integration and Software Development. Our assignment characteristically span over several areas and we do have the knowledge required to bridge the distance in between.

Cases

Optimizing simulator's execution time

This case is a story of how Stickybit found a way to turn a worrying situation regarding performance of the system's simulator at a customer's site into a costs and time saving optimization that eventually increased throughput of the entire department. The customer was in fact so pleased that it let our engineer use some of his results in a paper for his (long overdue) master thesis. This is his story.

A simulation and verification department within a large company made use of a simulator written primarily in C++. It was strongly suspected that optimizations were possible in this simulator, as most of the developers responsible for the simulator were not domain experts in programming (most had a strong background in other fields, such as signal processing). Beyond the general suspicion, however, there was not much knowledge or evidence available about the nature of any specific improvements that might be made. Since an individual simulation could take between several hours and several dozen hours, even a modest improvement of 5% execution time would save considerable resources.

Therefore, the assignment with the client was to first analyze and profile the simulator, to discover the location and scope of any execution
bottlenecks. After identification of the problematic portions of code, an analysis would then be made about any possible improvements and/or
alternative implementations to lower execution cost.

Multiple profiling tools were evaluated for usage in this assignment, including both open source and proprietary software. The former
included gprof (part of the gcc compiler suite), cachegrind (a memory profiling modification of valgrind), and oprof (a Linux kernel-based
profiler). The latter focused primarily on quantify, part of the IBM Rational PurifyPlus suite.

Due to the sheer size and runtime of the simulator, it became quickly apparent that any profiling tool with significant (>= O(n)) execution
overhead would not be feasible for general usage. This unfortunately ruled out the tools with the best visualization support, Rational
Quantify and cachegrind. Cachegrind had an overhead of 5-20 times standard execution cost, whereas Quantify's overhead was between 5-10
times cost from empirical testing. Gprof, conversely, had an execution overhead that seemed to be closer to logarithmic and could
provide nearly the same level of detail as quantify (minus the graphical user-interface/visualization support).

Application profiling via gprof revealed several execution bottlenecks in the simulator. Most interesting was that in the majority of cases, the code was not expected to be on the critical path of the application profile. In some cases, the cost was due to a suboptimal implementation
of basic datastructures (queues where data was copied as opposed to pointers updated), and in other cases due to the use of the wrong
datastructure (queues instead of a circular buffer).

One notable improvement was found in such an unexpected part of the simulator. There were cases where suboptimal standard c-library math functions were used where a specialized use case could imply a specialized implementation for optimal performance. One such example was the use of the standard pow() function for calculating integer values of two within a relatively small range of -32 to 32 for specialized quantization functions. An alternative implementation made use of lookup-tables of pre-calculated values. This improvement alone resulted in a surprising speedup of 12% for typical simulations. For the average performance regression simulation this single improvement was equivalent to a savings of between 30 minutes and 60 minutes running time.

Additionally, along with the profiling assignment came a certain level of code review, which revealed a number of bugs and coding oversights, the fixes for which were incorporated into the simulator as part of the audit (but not counted towards the overall speedup)

Further possibilities for improvement were found elsewhere in the simulator, such as the speed improvements to the random number generator, the memory management system, and targeted use of function inlining and class templating. The delivered improvements reached approximately 15-20% with an additional set of recommendations for a possible 35% total improvement.