2

I need to find the number of operations that a specific algorithm is doing: assigns, increments, comparators of integers, comparators of floats, multiplications of integers, etc.

I'm doing this manually and even though feasible it's a lot of work. So, do you know of any tool that does this automatically or semi-automatically?

I'm asking this because there are specific cases when I can't (or it's very difficult to) manually discover the number of operations. For example, the algorithm has one qsort and looking at the confusing code of that function looks like a LOT of work.

Edit: In response to some comments on why do I want this. The objective in the future in to implement this algorithms that are currently on software in hardware language. So, as atan latency differs from multiplications or sum latency, it is very important to measure which algorithm has the correct number of operations to be converted into hardware-language.

João Pereira
  • 673
  • 1
  • 9
  • 29
  • 2
    What counts as “one operation” for you? – fuz Aug 28 '15 at 16:53
  • 1
    What is the motivation. – Ed Heal Aug 28 '15 at 16:55
  • You could get the dissassembly and use notepad++ or similar to count the number of occurrences of `ADDI` and other expressions ... – Fantastic Mr Fox Aug 28 '15 at 16:55
  • Why all the downvotes? While underspecified, this is a valid question. – fuz Aug 28 '15 at 16:56
  • @FUZxxl: Asking for a tool is a valid question? Did the rules change? And even if, the question is badly asked. OP does not exactly specify his Problem, what he wants to achieve, and what he has doe to find such a tool and why they do not work for her. – too honest for this site Aug 28 '15 at 16:57
  • I specified the various type of operations: assigns, increments, etc. And still you just downvote... Ok ty – João Pereira Aug 28 '15 at 16:57
  • You assume that it was me downvoting. Coincidetally, I did, but I'm not the only one. – too honest for this site Aug 28 '15 at 16:59
  • Take a look at the [`PetscLogFlops()`](http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Profiling/PetscLogFlops.html) of the Petsc library. Their profiling tools are interesting to know the number of floating point operations (flop). A tool similar to this one may suit your need. For, instance, use a global variable or add a field to your struct and increment it each time the `compare()` function is used when `qsort()` is called. – francis Aug 28 '15 at 17:01

2 Answers2

1

Depending on what you mean by 'operations', one way to do this would be to compile the program and then use gdb to find the number of assembly instructions being run.

Community
  • 1
  • 1
F. Stephen Q
  • 4,208
  • 1
  • 19
  • 42
  • I'm interested in different kinds of operations. All that take up processor resources regarding computational consumption. So basically, I'm trying to see how many assigns does each sub-function has, how many icnrements, how many comparators, etc. The objective in the end is to compare these number of operations with similar data from other algorithms so that one can say: so algorithm 1, which has X assigns, Y integer comparators, etc, takes Z1 seconds on a processor and Z2 seconds on a FPGA. – João Pereira Aug 28 '15 at 17:01
  • Assembly instructions are the lowest level of 'computational consumption' you will be able to measure. `gdb` is a great tool for learning more about assembly and investigating the instructions your program runs, but you can also [use your compiler to output readable assembly source](http://stackoverflow.com/questions/1289881/using-gcc-to-produce-readable-assembly). Due to the diversity of hardware, its hard to find how long any algorithm will take to run beyond its big-O efficiency class. While fewer instructions does usually mean faster code, not all instructions are equal. – F. Stephen Q Aug 28 '15 at 17:05
1

You can use a profiler to get a statistical summary of how often each instruction runs, and/or how many clock cycles each one takes.

For your purpose of seeing the actual sequence of instructions run by a function, what you want is called a trace. That's the sequence of instructions that actually ran, in order, including branch instructions. The simplest way would be to set a breakpoint in gdb, then stepi through the function you're interested in.

That's not viable for longer traces. There are automatic tools for doing this:

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • I'm going to read about those recommended tools, try and use them and if that's what I'm looking for I will mark this as answer. Thank you for the help ;) – João Pereira Aug 31 '15 at 14:55