How to write code which minimizes page faults?

[Sune]

Hi!

Pre-requisites:
-------------------
1) Consider I'm about to write a quite large program. Say 500 K
lines.
2) Part of this code will consist of 50 structs with, say, no more
than at most 1K bytes of data.
3) These structs are to be used by all of the other 500K lines in
various places.
4) Linux, SUN Solaris

Design decisions:
-------------------
- Add functions to the structs so they handle their own data. Kind of
C++ OOP.
- Just make the structs carry data, and write macros to handle the
data of each struct, and insert those macros in appropriate places
in the 500 K lines of code, wherever they are used.

This question does not deal in what is good programming in terms of
macros or OOP and data encapsulation in C!!!!! So please no remarks
on this unless it makes your answers to the questions below more
clear.

Question:
--------------------
- I'm afraid that adding code/functions to structs results in worse
locality, i.e. this will result in increased paging. Is that so?

- Is inserting code in the 500K lines wherever it's needed, worth
the effort? or am I over exaggerating the risk and consequences of
page faults?

Thanks in advance
/Sune

[EventHelix.com]

Use of object oriented programming should result it keeping related
code and data in close proximity. This would improve the locality
of reference for code as well as data.

Other than that, you should not worry about this issue. Do not
compromise readability and maintainability of code to achieve higher
locality of reference.

--
EventStudio 2.5 - http://www.EventHelix.com/EventStudio
Generate Sequence Diagrams in PDF and Word EMF from plain text input

[Sune]

Hi!

What you say makes sense, thanks for sharing.

IF ANYBODY HAS ANYTHING TO ADD, PLEASE DO. I'LL GO BACK TO THIS MESSAGE
ON AND OFF FOR 1-2 WEEKS.

BRs
/Olle

[Artie Gold]

Sune wrote:

Hi!

Pre-requisites:
-------------------
1) Consider I'm about to write a quite large program. Say 500 K
lines.
2) Part of this code will consist of 50 structs with, say, no more
than at most 1K bytes of data.
3) These structs are to be used by all of the other 500K lines in
various places.
4) Linux, SUN Solaris

Design decisions:
-------------------
- Add functions to the structs so they handle their own data. Kind of
C++ OOP.
- Just make the structs carry data, and write macros to handle the
data of each struct, and insert those macros in appropriate places
in the 500 K lines of code, wherever they are used.

This question does not deal in what is good programming in terms of
macros or OOP and data encapsulation in C!!!!! So please no remarks
on this unless it makes your answers to the questions below more
clear.

Question:
--------------------
- I'm afraid that adding code/functions to structs results in worse
locality, i.e. this will result in increased paging. Is that so?

- Is inserting code in the 500K lines wherever it's needed, worth
the effort? or am I over exaggerating the risk and consequences of
page faults?

Thanks in advance
/Sune

Unfortunately, none of the information you've provided says much about
what the (potential) paging behavior of your program will be -- assuming
there's any paging at all. (50 1K structs is a trivial amount, so,
likely, is the amount of machine code corresponding to a 500KLOC source.)

What is more significant here, assuming there's enough data where paging
becomes an issue, is the *pattern* in which data are accessed (this
often works in ways that are counterintuitiv e, BTW).

Perhaps the classic situation is as follows:
The amount of memory you have is M whatevers.
You access M + 1 whatevers of data in a loop -- i.e. just barely more
than will fit in memory.

If you count the number of page faults that would be generated using a
typical LRU replacement algorithm, you'll see that this is pretty much a
pessimal situation -- which absolutely *clobbers* performance.

If, in this situation, you were to split your loop so it only iterates
over half the memory at a time, the number of page faults would be
*drastically* reduced; in fact they would nearly be eliminated! [Doing
the calculation is a very worthwhile exercise.]

HTH,
--ag

--
Artie Gold -- Austin, Texas
http://it-matters.blogspot.com (new post 12/5)
http://www.cafepress.com/goldsays
"If you have nothing to hide, you're not trying!"

[Artie Gold]

Artie Gold wrote:

Sune wrote:

Hi!

Pre-requisites:
-------------------
1) Consider I'm about to write a quite large program. Say 500 K
lines.
2) Part of this code will consist of 50 structs with, say, no more
than at most 1K bytes of data.
3) These structs are to be used by all of the other 500K lines in
various places.
4) Linux, SUN Solaris

BTW - this is pretty OT. (Yup, I forgot where I was. Followups set.)

--ag

--
Artie Gold -- Austin, Texas
http://it-matters.blogspot.com (new post 12/5)
http://www.cafepress.com/goldsays
"If you have nothing to hide, you're not trying!"

[Malcolm]

"Sune" <su**********@h otmail.com> wrote

- I'm afraid that adding code/functions to structs results in worse
locality, i.e. this will result in increased paging. Is that so?
In C you cannot have functions as members of structs, in C++ you can.
There's quite a strong arument that if you want to hold your data in plain
structs, you should use C rather than C++. C++ people on comp.lang.c++ might
have more to say on this.

Once you move from plain data types, you begin to lose control of the way
your data is laid out in memory. It becomes much more difficult to keep
track of which data is accessed and when.
- Is inserting code in the 500K lines wherever it's needed, worth
the effort? or am I over exaggerating the risk and consequences of
page faults?

We cannot say.Is running time absolutely critical, and is the speed of
memory access the real culprit? Sometimes the answer will be yes, but it is
unusual and getting more unusual for these types of questions to dominate
design decisions.
Generally you should just lay out structures to make them readable, and
assume that the compiler does a reasonable job of putting them on
appropriate page boundaries. However sometimes it is worth trying to beat
the compiler to get that little bit of extra performance.

[Christian Bau]

In article <11************ **********@g44g 2000cwa.googleg roups.com>,
"Sune" <su**********@h otmail.com> wrote:

Hi!

Pre-requisites:
-------------------
1) Consider I'm about to write a quite large program. Say 500 K
lines.
2) Part of this code will consist of 50 structs with, say, no more
than at most 1K bytes of data.
3) These structs are to be used by all of the other 500K lines in
various places.
4) Linux, SUN Solaris

Design decisions:
-------------------
- Add functions to the structs so they handle their own data. Kind of
C++ OOP.
- Just make the structs carry data, and write macros to handle the
data of each struct, and insert those macros in appropriate places
in the 500 K lines of code, wherever they are used.

This question does not deal in what is good programming in terms of
macros or OOP and data encapsulation in C!!!!! So please no remarks
on this unless it makes your answers to the questions below more
clear.

Question:
--------------------
- I'm afraid that adding code/functions to structs results in worse
locality, i.e. this will result in increased paging. Is that so?

- Is inserting code in the 500K lines wherever it's needed, worth
the effort? or am I over exaggerating the risk and consequences of
page faults?

Would be better if you posted what you actually try to achieve.

If you try to keep a bunch of programmers busy for an extended amount of
time, modifying 500,000 lines of code and fixing all the bugs that you
introduce while making these changes seems a good idea. Who is going to
pay for it?

[akarl]

Sune wrote:

Pre-requisites:
-------------------
1) Consider I'm about to write a quite large program. Say 500 K
lines.
2) Part of this code will consist of 50 structs with, say, no more
than at most 1K bytes of data.
3) These structs are to be used by all of the other 500K lines in
various places.
4) Linux, SUN Solaris

Design decisions:
-------------------
- Add functions to the structs so they handle their own data. Kind of
C++ OOP.
- Just make the structs carry data, and write macros to handle the
data of each struct, and insert those macros in appropriate places
in the 500 K lines of code, wherever they are used.

This question does not deal in what is good programming in terms of
macros or OOP and data encapsulation in C!!!!! So please no remarks
on this unless it makes your answers to the questions below more
clear.

Question:
--------------------
- I'm afraid that adding code/functions to structs results in worse
locality, i.e. this will result in increased paging. Is that so?

- Is inserting code in the 500K lines wherever it's needed, worth
the effort? or am I over exaggerating the risk and consequences of
page faults?

Why do you want to use C (a high level assembler) for such a large program?

August

[E. Robert Tisdale]

Sune wrote:

Pre-requisites:
-------------------
1) Consider I'm about to write a quite large program.
Say 500 K lines.
2) Part of this code will consist of 50 structs
with, say, no more than at most 1K bytes of data.
3) These structs are to be used by all of the other 500K lines
in various places.
4) Linux, SUN Solaris

Design decisions:
-------------------
- Add functions to the structs so they handle their own data.
Kind of C++ OOP.
Don't do this.
- Just make the structs carry data
and write macros to handle the data of each struct
Use inline [static] functions instead.
and [use those inline functions] in appropriate places
in the 500 K lines of code, wherever they are used.

This question does not deal in what is good programming
in terms of macros or OOP and data encapsulation in C!
So please no remarks on this
unless it makes your answers to the questions below more clear.

Question:
--------------------
- I'm afraid that adding code/functions to structs results in worse
locality, i.e. this will result in increased paging. Is that so?
It's nonsense.
- Is inserting code in the 500K lines wherever it's needed
worth the effort?
Use inline [static] functions instead.
Or am I over exaggerating the risk and consequences of page faults?

Yes.

Just write code that is as clean and readable as possible.

You can't include functions in a struct.
You can include *pointers* to functions in structs
but *don't* do it unless you need run-time polymorphism.
If you need run-time polymorphism,
include a pointer to a "virtual function table" in your struct
then write inline [static] functions
to (de)reference the appropriate function from the table.

[Default User]

akarl wrote:

Why do you want to use C (a high level assembler) for such a large
program?

Why do you want to make false and ridiculous statements on newsgroups?


Brian