The Cyclomatic Horror From Outer Space

I don’t really remember how we got there, but a couple of days ago at the office we ended up talking about the complexity of the codebase we have to deal with. Tommi mentioned the McCabe cyclomatic complexity, “which may be considered a broad measure of soundness and confidence for a program“. According to the Wikipedia article it “directly measures the number of linearly independent paths through a program’s source code“. And there’s this little table, with some pre-defined thresholds:

1-10 a simple program, without much
11-20 more complex, moderate risk
21-50 complex, high risk program
greater than 50 untestable program (very high

Well, fair enough. You always have to be a little skeptic about this kind of data, but it might give you some insights about a codebase. So “apt-get install pmccabe”, a tool to “calculate McCabe cyclomatic complexity or non-commented line counts for C and C++ programs“. The man page says:

The obvious application of pmccabe is illustrated by the following which gives a list of the “top ten” most complex functions:

pmccabe *.c | sort -nr | head -10

Sounds like fun! Let’s run it on the gtk/ directory in gtk+… (drum rolls):

Cyclomatic complexity Lines of code Function name
119 337 gtk_notebook_calculate_tabs_allocation
119 744 gtk_tree_view_bin_expose
89 467 gtk_tree_view_column_cell_process_action
88 545 update_node (in gtkuimanager.c)
68 404 gtk_tree_view_button_press
68 381 gtk_toolbar_size_allocate
64 218 gtk_im_context_simple_filter_keypress
64 230 gtk_tree_view_key_press
59 243 gtk_menu_handle_scrolling
58 175 gtk_clist_motion

Some of the functions are way past the threshold for intractability (and all of them surpass it), and GtkTreeView has 4 of the 10 most complex functions in gtk according to McCabe. I suppose you can extract many lessons from here, but I’ll only give one humble suggestion: we need regression testing for gtk, and we need it yesterday, as it seems that no human being can hack on some parts of gtk without breaking something πŸ™‚

This entry was posted in General. Bookmark the permalink.

6 Responses to The Cyclomatic Horror From Outer Space

  1. kris says:

    Those tree view functions are not that hard once you get the hang of them πŸ™‚ Anyway, I’ve indeed been thinking about automatically testing most core GtkTreeView functionality, more on that later. I am surprised GtkTreeModelFilter didn’t show up in the table πŸ˜‰

  2. It will take some heavy refactoring before chunks of GTK+ can be automatically tested. For example, we’d need some standalone “layout calculator” for GtkCellRenderers that can be called by the test suite — right now that code is spread all over the place in GtkTreeView and cell renderers themselves.

  3. Pingback: RaphaΓ«l’s Last Minutes » Blog Archive » Cyclomatic complexity in GIMP code

  4. haypo says:

    Try it on libc with “find -name “*c”|xargs pmccabe >> ~/report; sort -nr /home/haypo/report |head”.

    Some hilarous results: 494 _IO_vfwscanf() ; 230 fnmatch() ; 222 strtod() ; 200 collate_read() ; 197 dl_main() ; 196 __isinfl_internal() (printf_fp.c) ; 175 wordexp()

  5. Haw, I can beat that – try GCC:
    1062 fold_binary
    485 find_reloads
    479 expand_expr_real_1
    430 simplify_binary_operation_1
    426 try_combine

    and these may not even be the worst instances, because it gets confused by a bunch of preprocessor abuse.

  6. You could take a look at MoMo, the Mozilla Monitor:
    (this one uses another tool, not pmccabe)

    The most complex function in an older version had 1323 McCabe, which beats GCC πŸ™‚
    Even the tenth in the row of the top 10 has complexity of 200. So keep on evolving….

Leave a Reply

Your email address will not be published. Required fields are marked *