To get a trial key
fill out the form below
Team License (standard version)
Enterprise License (extended version)
* By clicking this button you agree to our Privacy Policy statement

** This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.
Request our prices
New License
License Renewal
--Select currency--
USD
EUR
GBP
RUB
* By clicking this button you agree to our Privacy Policy statement

** This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.
To get the licence for your open-source project, please fill out this form
* By clicking this button you agree to our Privacy Policy statement

** This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.
To get the licence for your open-source project, please fill out this form
* By clicking this button you agree to our Privacy Policy statement

** This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.
I am interested to try it on the platforms:
* By clicking this button you agree to our Privacy Policy statement

** This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.
Message submitted.

Your message has been sent. We will email you at


If you haven't received our response, please do the following:
check your Spam/Junk folder and click the "Not Spam" button for our message.
This way, you won't miss messages from our team in the future.

>
>
Ineffectiveness of last() in the real w…

Ineffectiveness of last() in the real world

Feb 09 2009
Author:

While studying at the institute and learning different data processing algorithms, I already knew that the necessity of using such a function as last() for one-way list can indicate an unfortunate choice of the data structure and lead to ineffective algorithm. Although I knew it long ago, I haven't faced this in practice until recently.

It began with a complaint that the static analyzer Viva64 hangs when analyzing one project, or rather one file of the project. Analysis showed that the analyzer doesn't hang at all and on the contrary works very hard. Very hard and very long. I think even this analyzer can analyze it successfully in approximately 5 or 10 hours :). But this became clear later and of course such behavior should be considered an error.

Frankly speaking, at the beginning I was astonished by this behavior. Viva64 analyzer operates rather quickly, and average time of analyzing one file takes just a few seconds. And its operating time is much less than time needed for preprocessing files. Preprocessing is executed by Visual C++ compiler and we cannot speed up this process yet. That's why, roughly speaking, the time of testing a project is close to the time of preprocessing all the files. And suddenly we discover such a great ineffectiveness in the analysis algorithm!

Investigations showed that hanging occurs when processing the file which contains some resources from Qt library, more exactly array whose size... well, I don't know its size, but I know that this is the largest array I've ever seen. It looks as follows:

static const unsigned char qt_resource_data[] = {
  0x0,0x0,0x0,0xc5,
  0x51,
  0x46,0x72,0x61,0x6d,0x65,0x20,0x7b,
  0xd,0xa,0x20,0x20,0x20,0x20,0x6d,0x69,0x6e,
  0x2d,0x77,0x69,0x64,0x74,0x68,0x3a,0x20,
  0x36,0x70,0x78,0x3b,0xd,0xa,0x20,0x20,
  0x20,0x20,0x6d,0x69,0x6e,0x2d,0x68,0x65,
  0x69,0x67,0x68,0x74,0x3a,0x20,0x36,0x30,
  . . .

This array occupies about 9 Mb in the file. This is a lot but it's not reason for the analyzer for such a bad behavior.

The problem was the already mentioned last() function. Viva64 analyzer is built on VivaCore library. And VivaCore is built in its turn on OpenC++ library from which it inherited data representation as trees and lists. By the way, data processing in OpenC++ (and VivaCore as well) reminds a lisp program very much. There are a lot of functions of the type like Eq, Car, Cdr, First, Rest, Second, Nth, List etc.

And there is also last() function which is used when creating a list of items for initializing the array. In the pseudocode it looks like this:

while (some items still remain)
{
  Ptree *e = to take another item;
  Ptree *last = Last(eList);
  last->SetCdr(Cons(e, 0));
}

In general the point is to take the following array's item and add it to the end of the list. To simplify search of the end we use last() function. OpenC++'s author obviously didn't suggest that the algorithm will be forced to process the array of millions of items. On small arrays it's OK, but to the time of such an algorithm increases in proportion to the squared number of items (to be more exact - the triangular number 0.5 * n * (n + 1), where n is the number of items).

The simplest optimization consisting in keeping the pointer to the last item of the list (what allows you not to call last() function) literally worked a miracle. Processing of the file which earlier took more than 3 hours (I didn't manage to wait more than 3 hours :), now takes several seconds.

Well, all we can say - be careful before you use functions like last(). You can never tell what your algorithm will be sooner or later palmed off. I wish you luck in optimization!

Popular related articles
The Evil within the Comparison Functions

Date: May 19 2017

Author: Andrey Karpov

Perhaps, readers remember my article titled "Last line effect". It describes a pattern I've once noticed: in most cases programmers make an error in the last line of similar text blocks. Now I want t…
Static analysis as part of the development process in Unreal Engine

Date: Jun 27 2017

Author: Andrey Karpov

Unreal Engine continues to develop as new code is added and previously written code is changed. What is the inevitable consequence of ongoing development in a project? The emergence of new bugs in th…
Appreciate Static Code Analysis!

Date: Oct 16 2017

Author: Andrey Karpov

I am really astonished by the capabilities of static code analysis even though I am one of the developers of PVS-Studio analyzer myself. The tool surprised me the other day as it turned out to be sma…
Free PVS-Studio for those who develops open source projects

Date: Dec 22 2018

Author: Andrey Karpov

On the New 2019 year's eve, a PVS-Studio team decided to make a nice gift for all contributors of open-source projects hosted on GitHub, GitLab or Bitbucket. They are given free usage of PVS-Studio s…
The Last Line Effect

Date: May 31 2014

Author: Andrey Karpov

I have studied many errors caused by the use of the Copy-Paste method, and can assure you that programmers most often tend to make mistakes in the last fragment of a homogeneous code block. I have ne…
PVS-Studio ROI

Date: Jan 30 2019

Author: Andrey Karpov

Occasionally, we're asked a question, what monetary value the company will receive from using PVS-Studio. We decided to draw up a response in the form of an article and provide tables, which will sho…
Technologies used in the PVS-Studio code analyzer for finding bugs and potential vulnerabilities

Date: Nov 21 2018

Author: Andrey Karpov

A brief description of technologies used in the PVS-Studio tool, which let us effectively detect a large number of error patterns and potential vulnerabilities. The article describes the implementati…
Characteristics of PVS-Studio Analyzer by the Example of EFL Core Libraries, 10-15% of False Positives

Date: Jul 31 2017

Author: Andrey Karpov

After I wrote quite a big article about the analysis of the Tizen OS code, I received a large number of questions concerning the percentage of false positives and the density of errors (how many erro…
The way static analyzers fight against false positives, and why they do it

Date: Mar 20 2017

Author: Andrey Karpov

In my previous article I wrote that I don't like the approach of evaluating the efficiency of static analyzers with the help of synthetic tests. In that article, I give the example of a code fragment…
PVS-Studio for Java

Date: Jan 17 2019

Author: Andrey Karpov

In the seventh version of the PVS-Studio static analyzer, we added support of the Java language. It's time for a brief story of how we've started making support of the Java language, how far we've co…

Comments (0)

Next comments

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.
This website uses cookies and other technology to provide you a more personalized experience. By continuing the view of our web-pages you accept the terms of using these files. If you don't want your personal data to be processed, please, leave this site.
Learn More →
Accept