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

Request our prices
New License
License Renewal
--Select currency--
USD
EUR
GBP
RUB
* By clicking this button you agree to our Privacy Policy statement

Free PVS-Studio license for Microsoft MVP specialists
* By clicking this button you agree to our Privacy Policy statement

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

I am interested to try it on the platforms:
* By clicking this button you agree to our Privacy Policy statement

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.

>
>
>
Viva64 for optimizing data structures

Viva64 for optimizing data structures

Feb 16 2009
Author:

Finally I've come to implementation of diagnosis in Viva64 analyzer detecting structures with non-optimal arrangement of fields. Absence in VivaCore of support of type calculations for small data types as ST_CHAR, ST_SHORT restrained me from that. Earlier all the types smaller than 32-bit were called ST_LESS_INT. So the library users should download an updated version of VivaCore. Everything has been changed in it recently.

But let's return to testing optimality of arrangement of data in structures. I will focus mostly on Visual C++. You know that data in C++ structures are aligned in such a way as to provide the most effective access to them. By the way, some microprocessors cannot address non-aligned data directly at all and the compiler has to generate special code for addressing such data. Those microprocessors which can address non-aligned data still do this much less effectively. That's why the C++ compiler leaves empty cells between fields of structures to align them according to the addresses of machine words and thereby speed up addressing to them. You can turn off the alignment function by using special directives #pragma to reduce the size of main memory being used but we are not interested in this variant now. It is often possible to significantly reduce the size of used memory by simply changing the order of fields in a structure without performance loss.

Let's consider the following structure:

struct MyStruct
{
  bool m_bool;
  char *m_pointer;
  int m_int;
};

On a 32-bit system this structure will occupy 12 bytes and it is impossible to reduce this size. Each field is aligned at the border of 4 bytes. Even if we put m_bool in the end it won't change anything. The compiler will still make the structure's size multiple of 4 bytes to align these structures in arrays.

In case of a 64-bit building MyStruct structure will occupy 24 bytes. It is clear why. In the beginning there is one byte under m_bool and 7 non-used bytes for alignment as the pointer occupies 8 bytes and must be aligned at the border of 8 bytes. Then there are 4 bytes m_int and 4 non-used bytes for aligning the structure at the border of 8 bytes. Fortunately, it can be easily corrected by putting m_bool in the end of the structure as follows:

struct MyStructOpt
{
  char *m_pointer;
  int m_int;
  bool m_bool;
};

MyStructOpt occupies not 24 but 16 bytes. It is a sensible saving if we use, for example, 10 million items. In this case we will save 80 MB of memory but what is more important, we can increase performance. If there are not to many structures it doesn't matter of what size they are. Access will be performed with the same speed. But when there are a lot of items cache, the number of memory accesses etc will do make the difference. And we can for sure say that processing of 160 MB of data will take less time than in case of 240 MB. Even a simple access to all the items of the array for reading will be rather fast.

I know that changing the order of fields in structures is not always possible or convenient. But if you have millions of such structures you should pay a little time to it. The results of such simple optimization as changing the order of fields can very significant. Now I haven't figures to prove this, but perhaps I will give examples in the next notes in the blog.

Perhaps you will ask according to what rules the compiler aligns data. I will give a brief answer but if you want to learn about this issue more, please address the book by Jeffrey Richter - "Programming Applications for Microsoft Windows, 4th edition". It seems to me that this question is considered there in detail.

In whole the alignment rule is the following: each field is aligned at the address multiple of the size of this field. On a 64-bit system the field of size_t type will be aligned at the border of 8 bytes, int at the border of 4 bytes and short at the border of 2 bytes. The fields of char type are not aligned. The size of a structure is aligned up to the size multiple of the size of its maximum item. Let's show it with the help of the following example:

struct ABCD
{
  size_t m_a;
  char m_b;
};

The items will occupy 8 + 1 = 9 bytes. But if the size of the structure is 9 bytes, that is, if we want to create an array of the structures ABCD[2], m_a field of the second structure will be placed at the non-aligned address. Because of this the compiler will add 7 empty bytes to the structure to reach the size of 16 bytes.

The process of optimizing the fields' sequence may seem complicated. But we can offer a very simple and very effective way. You can just arrange the fields in descending order according to their sizes. It will be absolutely enough. In this case the fields will be situated without additional gaps. For example, let's take the following structure of 40 bytes

struct MyStruct
{
  int m_int;
  size_t m_size_t;
  short m_short;
  void *m_ptr;
  char m_char;
};

and with the help of simple size-descending sort of the fields' sequence:

struct MyStructOpt
{
  void *m_ptr;
  size_t m_size_t;
  int m_int;
  short m_short;
  char m_char;
};

we will make a structure of only 24 bytes.

A much more difficult task is detection of these very structures that should be modified. It is a thankless and tiresome task to look through all the structures and classes. It is for this purpose that I came to adding rules for searching such ineffective structures (classes) into Viva64. Besides, the analyzer will show some intelligence by giving no warning messages on the classes which are descendants of other classes. Usually such objects are not created in millions. That is, I want the analyzer to warn about ineffectiveness of MyPoint class but to keep silent about ineffectiveness of MyWindow class:

class MyPoint {
  bool m_isActive;
  size_t m_x, m_y;
  char m_color[3];
  ...
};
class MyWindow : public CWnd {
  bool m_isActive;
  size_t m_sizeX, m_ sizeY;
  char m_color[3];
  ...
};
Popular related articles
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…
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…
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…
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…
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…
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…
The Ultimate Question of Programming, Refactoring, and Everything

Date: Apr 14 2016

Author: Andrey Karpov

Yes, you've guessed correctly - the answer is "42". In this article you will find 42 recommendations about coding in C++ that can help a programmer avoid a lot of errors, save time and effort. The au…
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…
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…

Comments (0)

Next comments
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