Folded stacks

measurement hashing recursion

A sampling profiler recorded in which call chains it caught the program. The profile is stored in “folded” form, as flame-graph tools understand it: each line is a chain of functions from the outermost to the one that was running, separated by semicolons, followed after a space by how many times the profiler caught the program in exactly this chain.

Two numbers are needed for each function. Total: how many samples caught it anywhere on the stack; this is the time spent on the function together with everything it called. Self: how many samples caught it at the top of the stack, doing its own work. If a function calls itself and occurs in a chain several times, it is still one sample.

Print the total number of samples and the k functions with the largest “total”; on a tie the one with the larger “self” goes first, and then by name in byte order.

Input

The first line holds n and k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100). Then n lines: a chain and a number of samples (from 1 to 10⁶) separated by a space. Function names are non-empty, contain no semicolons and may contain spaces, so the number of samples is separated by the last space in the line. All the chains together take at most 4 MB.

Output

The first line holds the total number of samples. Then at most k lines: the function name, “total” and “self” separated by spaces.

Examples

Example 1

Input

6 5
main;load;read 30
main;sort;qsort;qsort;partition 25
main;sort;qsort;partition 20
main;sort;qsort;qsort;qsort;partition 10
main;report;format 10
main;sort;qsort 5

Output

100
main 100 0
qsort 60 5
sort 60 0
partition 55 55
read 30 30

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

“Self” is simply the last function in the chain. All the difficulty is in “total”: what happens if a function stands in a chain twice?

2The idea

Keep two dictionaries: name → “total” and name → “self”. For each line add its number to the “self” of the last function, and to the “total” of every function in the chain, but to each only once: first gather the names of the chain into a set. Then sort the names by the rule in the statement.

3Walkthrough

Why only once? “Total” answers the question: how much time passed while the function was on the stack, that is, how much would be saved if its call disappeared together with everything it does. A sample that caught a recursive function three calls deep is still a single instant. If you add for every occurrence, the recursive sort in the example gets 105 samples out of 100, and in a profile of recursive code “total” stops meaning anything at all. Real tools count the same way: the cum column in pprof and “total” in flame graphs.

The second and third tests are real profiles of the earthquake report from the article on profilers, in Python and in Go. In the Python profile module names like <frozen importlib._bootstrap> contain spaces, which is why the number is separated by the last space rather than the first.

3+Solution

4Complexity

O(L + F log F), where L is the length of the input and F the number of distinct functions: one pass over all names and a sort.

5Common mistakes

Recursion counted twice. A function gets more samples than there were in all; the fourth test has recursion up to forty deep.
Splitting at the first space. Breaks on the names with spaces in the second test.
The tie order. First “total”, then “self”, then the name: the fifth test consists of ties.

Algorithms behind it

TEC Technique Profilers Don’t guess where a program spends its time, look: a sampling profiler, cProfile and pprof, the flame graph. a function’s share ± √(p(1−p)/N) 1 problem DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems