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 counterintuitive, 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**********@hotmail.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**********************@g44g2000cwa.googlegroups .com>,
"Sune" <su**********@hotmail.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

[Malcolm]

"akarl" <fu********@comhem.se> wrote

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

C++ is a good language for many complex projects. It doesn't follow that C
is a bad or worse language for such projects.

[akarl]

Default User wrote:

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?

No, let me rephrase that:

Why do you want to use a low-level and unsafe programming language
for a project of this size?

It's not a rant, I'm only curious.
August

[Walter Roberson]

In article <as*******************@newsb.telia.net>,
akarl <fu********@comhem.se> wrote:

let me rephrase that: Why do you want to use a low-level and unsafe programming language
for a project of this size? It's not a rant, I'm only curious.

Would it be better if they were to do the proposed project in LISP ?
APL? perl ?
--
Any sufficiently old bug becomes a feature.

[Default User]

akarl wrote:

Why do you want to use a low-level and unsafe programming language
for a project of this size?
Why would you bother to post to a newsgroup dedicated to a language you
despise.
It's not a rant, I'm only curious.

It's more a troll, I'd say. So,
*plonk*


Brian

[akarl]

Default User wrote:

akarl wrote:

Why do you want to use a low-level and unsafe programming language
for a project of this size?

Why would you bother to post to a newsgroup dedicated to a language you
despise.

I don't. I think C is good for making small, efficient and/or low-level
programs.

It's not a rant, I'm only curious.

It's more a troll, I'd say. So,

The comp.lang.* groups are not only for religious followers of one
language, you know. I would certainly be a troll if I said that C sucks
in every respect, but I haven't.

Since neither you nor Sune seem to be able to answer my question you
probably have no good answer, so I won't be bothering you with it.
August

[Richard Bos]

akarl <fu********@comhem.se> wrote:

Default User wrote:

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?

No, let me rephrase that:

Why do you want to use a low-level and unsafe programming language
for a project of this size?

Let me, then, rephrase Brian's reply to fit your rephrased question:

Why do you want to make false and ridiculous statements on newsgroups?
It's not a rant, I'm only curious.

Feh.

Richard

[Sune]

Hi guys!

Thanks for giving me insight on a non-issue it seems. I'm usually a C++
programmer so that's why some of my suggestions went off topic (like
functions in structs).

The reason I need info on C is that I'm rather fed up with OO and think
I can achieve the same abstractions and the necessary level of
encapsulation in C without having to instantiate 25-100 objects in the
traffical path.

I believe C with small intelligent C++ objects is the way to
go...together with exceptions, RAII etc. Nice mix I think...

BRs
/Olle

[Malcolm]

"akarl" <fu********@comhem.se> wrote in message
news:vP*******************@newsb.telia.net...

Default User wrote:

akarl wrote:

Why do you want to use a low-level and unsafe programming language for a
project of this size?

Since neither you nor Sune seem to be able to answer my question you
probably have no good answer, so I won't be bothering you with it.

C is a simple language, so maintenance and configuration is easy. That's
what you probably mean by "low level".
All programming languages are unsafe, in that none can guarantee that the
programmer hasn't made an error. Since C is so simple, mistakes are unlikely
to be due to some quirk of the language.

[akarl]

Malcolm wrote:

"akarl" <fu********@comhem.se> wrote in message
news:vP*******************@newsb.telia.net...

Default User wrote:

akarl wrote:

Why do you want to use a low-level and unsafe programming language for a
project of this size?
Since neither you nor Sune seem to be able to answer my question you
probably have no good answer, so I won't be bothering you with it.

C is a simple language, so maintenance and configuration is easy. That's
what you probably mean by "low level".

No, I mean direct memory access, raw pointers etc.
All programming languages are unsafe, in that none can guarantee that the
programmer hasn't made an error.
A safe language is a language where a large class of errors are detected
when they occur and not when data gets corrupted. Such a language
provides e.g. array bounds checking, garbage collection and restricted
pointers.

Since C is so simple, mistakes are unlikely to be due to some quirk of the language.

Lots of laughs. You're being ironic I hope. The quirks of C is part of
it's charm and success. If you want to see a *real* simple (procedural)
language, check out Oberon-2.

August

[Gordon Burditt]

>> All programming languages are unsafe, in that none can guarantee that the

programmer hasn't made an error.

Unless, of course, it is impossible to make an error. Consider an
assembly language with one-bit opcodes, NOOP and HALT, which can
be arranged in any order. (A HALT opcode is implied if you run
off the end of the program.) Of course, you can't do anything
USEFUL with it, either. All those ugly things that cause errors
like pointers, variables, arithmetic, loops, etc. are prohibited.

Gordon L. Burditt

[Keith Thompson]

go***********@burditt.org (Gordon Burditt) writes:

All programming languages are unsafe, in that none can guarantee that the
programmer hasn't made an error.

Unless, of course, it is impossible to make an error. Consider an
assembly language with one-bit opcodes, NOOP and HALT, which can
be arranged in any order. (A HALT opcode is implied if you run
off the end of the program.) Of course, you can't do anything
USEFUL with it, either. All those ugly things that cause errors
like pointers, variables, arithmetic, loops, etc. are prohibited.

Or, equally useful, my own language "99".

<http://www.99-bottles-of-beer.net/language-99-804.html>

The real challenge would be to design a *useful* language in which
errors, or at least some significant class of errors, are impossible.
Such a language might be possible, but I wouldn't expect it to have C
as one of its direct ancestors.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[akarl]

Gordon Burditt wrote:

All programming languages are unsafe, in that none can guarantee that the
programmer hasn't made an error.

Unless, of course, it is impossible to make an error. Consider an
assembly language with one-bit opcodes, NOOP and HALT, which can
be arranged in any order. (A HALT opcode is implied if you run
off the end of the program.) Of course, you can't do anything
USEFUL with it, either. All those ugly things that cause errors
like pointers, variables, arithmetic, loops, etc. are prohibited.

(You replied to the wrong message; *Malcolm* said: "All programming
languages are unsafe...")

[CBFalconer]

Keith Thompson wrote:

.... snip ...
The real challenge would be to design a *useful* language in which
errors, or at least some significant class of errors, are impossible.
Such a language might be possible, but I wouldn't expect it to have C
as one of its direct ancestors.

To my mind we have had that language for many years. Pascal. When
able to call C routines virtually all limitations disappear. And
for the last measure of flexibility, we allow C routines to call
assembly routines.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Charles Richmond]

CBFalconer wrote:

Keith Thompson wrote:

... snip ...

The real challenge would be to design a *useful* language in which
errors, or at least some significant class of errors, are impossible.
Such a language might be possible, but I wouldn't expect it to have C
as one of its direct ancestors.

To my mind we have had that language for many years. Pascal. When
able to call C routines virtually all limitations disappear. And
for the last measure of flexibility, we allow C routines to call
assembly routines.

"It's often been said that C gives you all the power and
flexibility of assembly language combined with all the
readability and maintainability of assembly language."

--
+----------------------------------------------------------------+
| Charles and Francis Richmond It is moral cowardice to leave |
| undone what one perceives right |
| richmond at plano dot net to do. -- Confucius |
+----------------------------------------------------------------+

[Malcolm]

"akarl" <fu********@comhem.se> wrote

All programming languages are unsafe, in that none can guarantee that the
programmer hasn't made an error.

A safe language is a language where a large class of errors are detected
when they occur and not when data gets corrupted. Such a language provides
e.g. array bounds checking, garbage collection and restricted pointers.

A compiler can potentially pick it up when a programmer says "this plane's
altitude is a grabage value". What it can never pick up is when the
programmer inadvertently says "let's do a controlled flight into terrain".
The second class of error is far more dangerous. Many language introduce
complications to reduce the chance of the first type of error, but thereby
increase the chance of error type two.

[CBFalconer]

Malcolm wrote:

"akarl" <fu********@comhem.se> wrote

All programming languages are unsafe, in that none can guarantee
that the programmer hasn't made an error.

A safe language is a language where a large class of errors are
detected when they occur and not when data gets corrupted. Such a
language provides e.g. array bounds checking, garbage collection
and restricted pointers.

A compiler can potentially pick it up when a programmer says "this
plane's altitude is a grabage value". What it can never pick up is
when the programmer inadvertently says "let's do a controlled
flight into terrain". The second class of error is far more
dangerous. Many language introduce complications to reduce the
chance of the first type of error, but thereby increase the chance
of error type two.

Your last sentence is in error. You are really differentiating
between compile time and run time checks, IMO.

The problem is that most languages, apart from Ada and Pascal, are
not closely typed. In both of those a strict limit can be set on
values in a given object, and conclusions drawn from that at
compile time. Thus if an object is limited to the range 0..4, the
result of squaring that value is guaranteed to fit into an object
limited to 0..16. This allows run time checks to be very
efficient, since things that can be proven at compile time need not
be checked at all, and the compiler can detect these cases.

C is also complicated by the abandoned use of pointers, making many
things inherently non-checkable. You just don't get latitude to do
anything at all without penalty.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Lawrence Kirby]

On Sun, 24 Jul 2005 10:20:11 -0700, EventHelix.com wrote:

Use of object oriented programming should result it keeping related
code and data in close proximity.
Doubtful. OO code tends to use dynamic allocation more. This tends to make
it slower, larger with less memory reuse. Dynamic memory datastructures
(the heap or whatever you choose to call it) are not likely to be kept
close to or interleaved with code. This is particularly nasty in languages
like Java where all full objects are dynamically allocated, perhaps not so
bad in C++.
This would improve the locality
of reference for code as well as data.
It is common for code and data to have separate caches at least for to
level caches on high performance processors. It is generally better to
keep code and data separated.
Other than that, you should not worry about this issue. Do not
compromise readability and maintainability of code to achieve higher
locality of reference.

Locality of reference is more about design of datastructures and
algorithms than anything else. The langauge and programming paradigm you
use does have an effect on this.

Lawrence

[mike]

akarl wrote:

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

Encapsulating C functions and structure var access is good practise
(IMHO) but it's not bullet proof! Besides a simple NULL check you're
limited in what you'll (personally) want to stuff in a macro, unless
this is what 500k is really going to consist of -- macro expansion.

I think it's safer to use HANDLES and have a private struct inside your
C file which will hold the actual data. Your header file will consist of
functions to access and manipulate that data (in a safe way).

My 200k C engine is based on this princable. I first create a header
file with all the function I think I'll require. e.g.

---> Header File

HANDLE Thing_Create();
BOOL Thing_Destroy( HANDLE Thing );
long Thing_Get_Stuff( HANDLE Thing, long lWhatStuff );

etc...

---> C File

//The private thing structure that contains the meat & veg.
//--------------------------------------------------------
typedef struct _Thing_tag_{
long lStuff1;
long lStuff2;
}Thing;

//The linked list structure that will hold all the things*
//-------------------------------------------------------
typedef strcut _ThingList_tag_{
struct _ThingList_tag_ *pNext;
struct _ThingList_tag_ *pPrev;
Thing theThing;
}ThingList;

//I create a head link pointer, to access the linked list (file scope).
//---------------------------------------------------------------------
static ThingList *pThingListHead = NULL;

//Thing_Create() function returns a handle, which essentially is a
//pointer. Because my structure is declared in the C file I can't
//simple cast it back from HANDLE to Thing, so i'm obliged to use
//the functions i made.
-----------------------------------------------------------
HANDLE Thing_Create(){

ThingLink *theThingLink = NULL;

1)..Allocate theThingLink using malloc().
2)..Set the initial values of theThingLink.
3)..Add (chain) the theThingLink to the to pThingListHead.

return (HANDLE) theThingLink;
}

//The most important aspect of Thing_Destroy() is no 1.
//---------------------------------------------------
BOOL Thing_Destroy( HANDLE Thing ){

1)..Check the HANDLE is valid, if not return FALSE.
2)..Unlink from the linked list
3)..Release the instance memory using free().

return TRUE;
}

//Any function that recieves the HANDLE (as Thing_Destroy() did) it
//should first call a HANDLE validation function...
//--------------------------------------------------------------------
BOOL Thing_Handle_Valid( HANDLE Thing ){

ThingLink *theThingLink = pThingLinkHead;

//Cycle all the links and search for the link.
while( theThingLink ){

//Check the addresses match.
if( (HANDLE) theThingLink == Thing )
return TRUE;

//Didn't match, get the next link.
theThingLink = theThingLink->pNext;
}

//No matching link found, this was a bogus HANDLE.
return FALSE;
}

--- EOCF ---
I've tried both approaches, using HANDLES and macros to protect &
encapsulate objects, in someway.

I've found, macros really come in handy when I need both == NULL
protection, speed & when I need to switch functions inside objects
dynamically.

As an example my engine is capable of switching between DirectX & OpenGL
in real time (back & forth). I have a macro to plot a pixel on the screen.

#define GRAPHICS_PLOT_PIXEL( gfxobject, x, y, c ){ \
(gfxobject != NULL ) ? gfxobject->PlotPixel( x, y, c ) : 0 \
}

Later when i need to switch the underlying implementation (From DirectX
to OpenGL or visa versa) I do:

gfxobject->PlotPixel = DirectX_Plot_Pixel

or

gfxobject->PlotPixel = OpenGL_Plot_Pixel

I could of course do this safer using functions calls, but they aren't
as fast as macros.

I suggest you use macros if speed & implementation switching is an
important issue, otherwise use HANDLES.

Or you could learn C++...!
-Mike