Sune wrote:

...

So now the only thing left is my questions    Maybe I don't know
enough to be able to ask the right things...

I allocate a page (page aligned) which starts on address 0xA000.
Immediately there is a header of 40 bytes. How should I place my
data ? For example if I assume I need to store my data in cache line
aligned this is what I need to do for question1 above:

*Why* do you assume you need to store your data cache line aligned?

Patricia

Responding to Sune...

this question is a bit of an odd ball I'm afraid. What I need to know
to be cache conscious when implementing a hash table is how an OS
Linux/UNIX reads data from RAM into a cache line.

Shanahan's advice is very good. However, I would like to push back on
why you want to optimize at this level at all...



Say I have a function blork with the following variables declared in
C:

void blork(void)
{
struct foo {
int var1;
int var2;
};

int var3;
int var4
....

Will the cache line look like this:
var1, var2, var3, var4....

or
var3, var4....

It is very difficult to optimize CPU caching at the 3GL level. You
really need to do it at the Assembly level. That's because the hardware
caching algorithm is optimized around the ALU pipeline and instruction
set so you really need to understand what instructions are used and what
their order is to do it properly. But a good 3GL optimizing compiler
will generate object code that is not at all intuitive from the source
listing and can be very difficult to understand. [Some compilers that
have an option to print line-by-line Assembly with the source do not
even optimize when they do that; the Assembly displayed is what you
would get in an unoptimized debug mode compilation. And that would not
do you much good.]

Essentially you need to look at the compiler's Assembly output and
design macros that will force access the of data in a preferred
instruction order given the CPU caching algorithm (in addition to
modifying the data structures to play well with the macros!). That would
be <relatively> easy in a language like BLISS that has a good macro
facility but it will be both very difficult and tedious in C.

In addition, such optimization will be very dependent on what you are
doing with the data. So if you access the same data in different
execution contexts (i.e., needing different instructions) the
optimization might be fine for one context but worse than the compiler's
way of doing things for another. IOW, you may need multiple sets of
macros for accessing the same data in different contexts.

Finally, a good 3GL optimizing compiler chooses instructions and puts
them in a particular order for good reasons. So optimizing the
instruction order just to optimize the CPU cache could negate the
compiler's attempts to optimize other things for a net loss in
performance -- though that should be rare unless the macros force
different instructions to be used. (I suggest using macros above because
you probably only want to override the compiler optimization in
particular situations.)

Corollary: Since such low level optimization is highly dependent on the
hardware platform, your optimization can become obsolete when the
hardware is upgraded. Thus your custom optimization may hard-wire in a
performance hit, especially if the compiler is also upgraded.

Bottom line: the days of ordering FORTRAN COMMONs by variable size and
using two additions rather than one multiplication by 3 are long gone.
It is usually not worth the trouble to do optimization at the CPU cache
level unless you have a highly specialized application. Generally
speaking, managing the overall memory access via things like nested loop
order is much more effective because the scale is larger, especially
when the application is large enough to have VM page faulting problems.

Usually you can do that by simply looking at your critical 3GL
procedures and viewing each data element access as loading a register
from memory. If you view those register loads as defining clumps of data
that should be close to adjacent in memory and/or all accessed in a
closed scope, you can then optimize your data structures, iterations,
and statements so that happens. (The optimizations one routinely does to
minimize VM page faulting are useful and usually will be sufficient,
even if VM paging itself isn't an issue.) Then the hardware caching
algorithm will almost always do the right thing.

FWIW I would not do such optimization unless I had hard data to indicate
it was really needed and I would look closely at the data to make sure
it wasn't the data collection itself that was skewing the results.
Unless you are doing embedded systems with a brain dead processor, have
hard real-time constraints, or have to use a cretinous C compiler, I
think it would be highly unlikely that worrying about the CPU cache
itself would be worthwhile.

--
Life is the only flaw in an otherwise perfect nonexistence
    -- Schopenhauer

H. S. Lahman
H.lah... at (no spam) verizon.net
software blog:http://pathfinderpeople.blogs.com/hslahman/index.html

Ok, point taken. But if we loose the alignment on the stack and just
go on to this:

I allocate a page (page aligned) which starts on address 0xA000.
Immediately there is a header of 40 bytes. How should I place my
data ? For example if I assume I need to store my data in cache line
aligned this is what I need to do for question1 above:

H is header
? is padding to make the data layout cache line aligned

0xA000:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH????????????????????????
0xA040:
DDDDDDDDDDDDDataElement1111111111111111111111111111111111???????????????
0xA080:
DDDDDDDDDDDDDataElement2222222222222222222222222222222???????????????
:

If I have a pointer referencing address 0xA050 (the E in DataElement1)
the following is read into the cache line:
DDDDDDDDDDDDDataElement1111111111111111111111111111111111???????????????

The reason for doing this would be to assure that I don't use 2 cache
lines for data that easily fits into 1.

Comments?

So now the only thing left is my questions Maybe I don't know
enough to be able to ask the right things...

I allocate a page (page aligned) which starts on address 0xA000.
Immediately there is a header of 40 bytes. How should I place my
data ? For example if I assume I need to store my data in cache line
aligned this is what I need to do for question1 above:

this question is a bit of an odd ball I'm afraid. What I need to know
to be cache conscious when implementing a hash table is how an OS
Linux/UNIX reads data from RAM into a cache line.

Say I have a function blork with the following variables declared in
C:

void blork(void)
{
struct foo {
int var1;
int var2;
};

int var3;
int var4
....

Will the cache line look like this:
var1, var2, var3, var4....

or
var3, var4....

The reason for doing this would be to assure that I don't use 2 cache
lines for data that easily fits into 1.

Comments?

Sune wrote:
...
The reason for doing this would be to assure that I don't use 2 cache
lines for data that easily fits into 1.

Comments?

You seem to be very focused on a single memory reference. That is
usually a mistake when thinking about caches. If you are not getting
*many* uses out of a typical cache miss you are in deep performance
trouble.

If your data structure and algorithms are such that you are doing a lot
of scattered references with no possibility of cache reuse, you need to
reexamine your choices at a far higher level.

On Sun, 23 Aug 2009 12:00:26 -0700, Patricia Shanahan wrote:

Sune wrote:
...
The reason for doing this would be to assure that I don't use 2 cache
lines for data that easily fits into 1.

Comments?
You seem to be very focused on a single memory reference. That is
usually a mistake when thinking about caches. If you are not getting
*many* uses out of a typical cache miss you are in deep performance
trouble.

If your data structure and algorithms are such that you are doing a lot
of scattered references with no possibility of cache reuse, you need to
reexamine your choices at a far higher level.

I agree with Patricia's advice:
0) "travel light": don't make your data structure larger than needed
1) once a cache slot is "faulted in" , make sure most of it's contents
are valuable to the program at that time: avoid pulling in a cache
line because you need only one byte.

Since your application appears to be a hashtable: in most cases linear
probing has a better locality then chaining.

this question is a bit of an odd ball I'm afraid. What I need to know
to be cache conscious when implementing a hash table is how an OS
Linux/UNIX reads data from RAM into a cache line.

Let's assume I have:
* a CPU with a cache line size of 64 bytes
* the page size of my OS set to 4 kb
* my OS is a 32-bit system
The bit-ness of a CPU or OS is meaningful description of anything.

* my own memory allocator serving me one full page at a time

How do I need to layout my data elements on a page to ensure they are
placed cache consciously?

1)
A page is allocated. It is empty apart from a page header of 40
bytes.

2)
I want to insert a Data element1 of 50 bytes into the page.

Questions:

1)
Do I need to align the page placement with my cache line size? Meaning
I have to write my element with an offset of 64 bytes from the page
start, leaving 14 bytes un-used?

Say I have a function blork with the following variables declared in
C:

void blork(void)
{
struct foo {
int var1;
int var2;
};

int var3;
int var4
....

Will the cache line look like this:
var1, var2, var3, var4....

or
var3, var4....

Say I have a function blork with the following variables declared in
C:

void blork(void)
{
struct foo {
int var1;
int var2;
};

int var3;
int var4
....

Will the cache line look like this:
var1, var2, var3, var4....

or
var3, var4....

There is no guarantee that the order of declaration of auto variables
has any effect at all on their ordering in memory. The ordering
might be based on a SHA-256 hash of the variable *name*. 4 ints
will usually fit in the same cache line.

this question is a bit of an odd ball I'm afraid. What I need to know
to be cache conscious when implementing a hash table is how an OS
Linux/UNIX reads data from RAM into a cache line.

The OS doesn't.  The CPU does.  It's handled at a level below the OS.
If there were cache-loading code, it's something you'd definitely want
in cache.

Let's assume I have:
* a CPU with a cache line size of 64 bytes
* the page size of my OS set to 4 kb
* my OS is a 32-bit system

The bit-ness of a CPU or OS is meaningful description of anything.
For example, 32-bit Windows and 32-bit Linux are *MUCH* more
different than 32-bit Linux and 64-bit Linux.

* my own memory allocator serving me one full page at a time
How do I need to layout my data elements on a page to ensure they are
placed cache consciously?

Place variables that are USED together PHYSICALLY together (e.g.
in the same struct), where possible.

1)
A page is allocated. It is empty apart from a page header of 40
bytes.

2)
I want to insert a Data element1 of 50 bytes into the page.

Questions:

1)
Do I need to align the page placement with my cache line size? Meaning
I have to write my element with an offset of 64 bytes from the page
start, leaving 14 bytes un-used?

First, performance is not required, so cache optimization is not
required.

One of the basic principles of cache *pessimization* is to spread
everything out so that no two variables are in the same cache line,
to maximize the number of cache misses.  A cache miss vs. a cache
hit is a much bigger performance difference than a variable at the
end of the cache line vs. a variable at the beginning of a cache
line.

Put variables that are used together physically together, so hopefully
they are in the same cache line.  Scan multi-dimensional arrays in
physical order if possible.



Say I have a function blork with the following variables declared in
C:

void blork(void)
{
struct foo {
int var1;
int var2;
};

int var3;
int var4
....

Will the cache line look like this:
var1, var2, var3, var4....

or
var3, var4....

There is no guarantee that the order of declaration of auto variables
has any effect at all on their ordering in memory.  The ordering
might be based on a SHA-256 hash of the variable *name*.  4 ints
will usually fit in the same cache line.

On 23 Aug, 19:19, Patricia Shanahan <p... at (no spam) acm.org> wrote:
Sune wrote:

...

So now the only thing left is my questions Maybe I don't know
enough to be able to ask the right things...
I allocate a page (page aligned) which starts on address 0xA000.
Immediately there is a header of 40 bytes. How should I place my
data ? For example if I assume I need to store my data in cache line
aligned this is what I need to do for question1 above:
*Why* do you assume you need to store your data cache line aligned?

Patricia

For example, this:
'INSN_CACHE_LINE_WIDTH
The length in bytes of each cache line. The cache is divided into
cache lines which are disjoint slots, each holding a contiguous chunk
of data fetched from memory. Each time data is brought into the cache,
an entire line is read at once. The data loaded into a cache line is
always aligned on a boundary equal to the line size. '

is stated about gcc here:
http://www.delorie.com/gnu/docs/gcc/gccint_136.html

Similar statements can be found here:
http://www.linuxshowcase.org/2000/2000papers/papers/sears/sears_html/

If I'm misinterpreting this I'd obviously need some support.

0xA000:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH????????????????????????
0xA040:
DDDDDDDDDDDDDataElement1111111111111111111111111111111111???????????????
0xA080:
DDDDDDDDDDDDDataElement2222222222222222222222222222222???????????????
:

If I have a pointer referencing address 0xA050 (the E in DataElement1)
the following is read into the cache line:
DDDDDDDDDDDDDataElement1111111111111111111111111111111111???????????????

The reason for doing this would be to assure that I don't use 2 cache
lines for data that easily fits into 1.

Comments?

Responding to Sune...

I allocate a page (page aligned) which starts on address 0xA000.
Immediately there is a header of 40 bytes. How should I place my
data ? For example if I assume I need to store my data in cache line
aligned this is what I need to do for question1 above:

H is header
? is padding to make the data layout cache line aligned

0xA000:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH????????????????????????
0xA040:
DDDDDDDDDDDDDataElement1111111111111111111111111111111111???????????????
0xA080:
DDDDDDDDDDDDDataElement2222222222222222222222222222222???????????????
:

If I have a pointer referencing address 0xA050 (the E in DataElement1)
the following is read into the cache line:
DDDDDDDDDDDDDataElement1111111111111111111111111111111111???????????????

That's not necessarily true. The hardware is only going to suck into its
cache lines the data that it needs to load into registers. If it doesn't
see a need to load data, it won't put it in the cache. So I would bet
that the E will be in the beginning of a cache line if you just
reference that pointer in your C code. OTOH, if it sees a need to load
more than 64 bytes of data, it will load multiple, consecutive cache
lines from main memory without any padding. That sort of anticipatory
buffering for things like string processing is why the CPU cache line
size is bigger than a machine word (32-bits on your machine).