Richard | 1 Jul 2010 07:12
Favicon
Gravatar

The effect of cache on performance

I stumbled across this today and found it an interesting read.
<http://queue.acm.org/detail.cfm?id=1814327>

It relates to our "virtual function calls are bad!"[*] discussion
earlier.

[*] they're not really bad, its cache misses that are bad.
--

-- 
"The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download
 <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/>

      Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Gregory Junker | 1 Jul 2010 07:30

Re: The effect of cache on performance

I thought this was a given?

> [*] they're not really bad, its cache misses that are bad.

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Richard Fabian | 1 Jul 2010 10:12
Picon
Gravatar

Re: The effect of cache on performance

Any development approach where you don't consider the effect of the cache is going to have inferior performance to one that either implicitly, or explicitly, takes advantage of the cache.


I do feel like we've been taught a lot of really good coding techniques that have ignored this issue. It doesn't mean that the code oriented techniques aren't good, for fast memory hardware our coding style and experience is invaluable.

On 1 July 2010 06:12, Richard <legalize <at> xmission.com> wrote:
I stumbled across this today and found it an interesting read.
<http://queue.acm.org/detail.cfm?id=1814327>

It relates to our "virtual function calls are bad!"[*] discussion
earlier.

[*] they're not really bad, its cache misses that are bad.
--
"The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download
 <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/>

     Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com



--
fabs();
Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
OvermindDL1 | 1 Jul 2010 23:50
Picon

Re: c++ reflection (was (no subject))

On Tue, Jun 29, 2010 at 8:49 PM, Sylvain Vignaud <vignsyl <at> iit.edu> wrote:
> Not sure anyone is still following this thread. I've just spent 10mn to
> improve the interface so that the Member macro doesn't have such a rigid
> number of arguments:
>
> I think the following code is quite easily expandable, and it now looks
> quite much like what Jarkko wanted: easy to have lots of parameters, no code
> generation tool, no precompilation pass.
>
> class Foo
> {
> public:
>     Foo() {}
>     virtual ~Foo() {}
>
> private:
>     DefineClass(Foo);
>
>     Member(int, test, Default(0); Description("Some int") );
>     Member(char *, mName, Default("foo"); Description("Some static text");
> Serialized());
>
>     Member(int*, mBuffer, Default(NULL), Description("Some ptr to nowhere");
> Serialized());
>
>     Member(int, foo);
>
>     Member(int, foo2, Description("this one has a desc, unlike foo"));
>     Member(int, foo3, Default(0xDead));
>
>     EndClass();
> };
>
> Updated code is still in the same place:
> http://tfpsly.free.fr/Files/Reflection.cpp
>
>
>
> On 24/06/10 00:24, Sylvain G. Vignaud wrote:
>
> Actually you can get something quite similar if you're not too regarding on
> mixing metaprogramming and macros. The result looks like:
> 	class Foo
> 	{
> 	public:
> 		Foo() {}
> 		virtual ~Foo() {}
> 	private:
> 		DefineClass(Foo);
> 	
> 		Member(int, test, 0);
> 		Member(char *, mName, "foo");
> 	
> 		Member(int*, mBuffer, NULL);
> 	
> 		EndClass(Foo);
> 	};
> 	Foo foo;
> 	foo.InitializeMembersToDefaultValue();
> 	const Foo::ClassDescription &desc = Foo::GetClassDescription();
> 	printf("type: %s\n", desc.name());
> 	printf("size: %d\n", desc.size());
> 	for( int i=0; i<Foo::NbrMembers; ++i )
> 	{
> 		const member_t &member = desc.m_Members[i];
> 		printf("  %s: offset %d  size %d  type %s\n",
> 			member.name, member.offset,
> 			member.type->size(), member.type->name());
> 	}
> And it seems the "Member" macro doesn't prevent Intellisense and the likes
> to know about members :)
> Also it could be expended to take more parameters, like a flag to decide
> which members are serialized, a text description...
> Quick proof of concept with full code - hacked using Jon Watte's
> Reflexion.cpp as a basis:
> http://tfpsly.free.fr/Files/Reflection.cpp
> From: Jarkko Lempiainen [Profoundic] <jarkko
>
> [...] But it would be nicer to have something like:
> struct my_struct
> {
>   int a {serialized, editable, desc("Car velocity"), color(0x123456)};
>   int b {serialized, editable, call(foobar())};
>   int c, d, e {serialized};
>   int f; // non-reflected variable
> };
> Cheers, Jarkko
> From: sweng-gamedev-bounces <at> lists.midnightryder.com
> [mailto:sweng-gamedev-bounces <at> lists.midnightryder.com] On Behalf Of Jon
> Watte
> Sent: Thursday, June 17, 2010 1:13 AM
> Am 17.06.2010 00:12, schrieb Jon Watte:
>
> Mail formatting still all messed up :-(
> Anyway, the example you had (PFC_MONO()) doesn't actually add all the
> annotations you want for editing and serialization in addition to the
> general reflection information.
> You can get rid of the ellipsis requirement by doing something like:
> #define MEMBERS(Type, x) \
>   typedef mytype Type; \
>   inline static Member *GetMembers() { \
>     static Member<mytype>[] members = { \
>       x \
>     }; \
>     return x; \
>   }
> #define MEMBER(x, desc) Member<mytype>(&mytype::x, #x, desc),
> Use it like so:
> struct MyStruct {
>   int x;
>   float b;
>   MEMBERS(MyStruct,
>     MEMBER(x, "Some integer value")
>     MEMBER(b, "The amount of float-ness"))
> };
> Note that the comma lives in the MEMBER() macro, and the members are
> just listed without comma within the MEMBERS() macro. The MEMBER()
> macro should take the union of all information you need about the
> member (editor information, networking, etc).

Still seems like it has a lot of oddity in its syntax, what about
something like this, which is completely possible and rather easily
done actually:

class Foo
{
public:
    Foo() {}
    virtual ~Foo() {}

private:
    DefineClass(Foo); // Why not make this define the actual class in
its entirety?

    Member((type(int))(name(test))(default(0))(description("Some int"));
    Member((type(char*))(name(mName))(default("foo"))(description("Some
static text"))(serialized));

    Member((type(int*))(name(mBuffer))(default(NULL))(description("Some
ptr to nowhere"))(serialized);

    Member((type(int))(name(foo)));

    Member((type(int))(name(foo2))(description("this one has a desc,
unlike foo")));
    Member((type(int))(name(foo3))(default(0xDead)));

    EndClass();
};

That style lets you add new capabilities arbitrarily without
introducing new Member overloads or what-not, just adding a keyword,
simple to do.  Or if you want to use the Boost proposed Mirror C++
reflection library, it would be this (this is non-intrusive for note):

class Foo
{
public:
    Foo() {}
    virtual ~Foo() {}

    int test;
    char *mName;

    int *mBuffer;

    int foo;

    int foo2;

    int get_foo3() const;
    void set_foo3(const int i);

    float someFunc(int);

private:
    int foo3;
};

BOOST_MIRROR_REG_BEGIN

BOOST_MIRROR_REG_CLASS_GLOBAL_SCOPE_BEGIN(class, foo)
  BOOST_MIRROR_REG_CLASS_MEM_VARS_BEGIN
    BOOST_MIRROR_REG_CLASS_MEM_VAR(public, _, _, test)
    BOOST_MIRROR_REG_CLASS_MEM_VAR(public, _, _, mName)
    BOOST_MIRROR_REG_CLASS_MEM_VAR(public, _, _, mBuffer)
    BOOST_MIRROR_REG_CLASS_MEM_VAR(public, _, _, foo)
    BOOST_MIRROR_REG_CLASS_MEM_VAR(public, _, _, foo2)
    BOOST_MIRROR_REG_CLASS_MEM_VAR_GET_SET(
        private,
        _, int, foo3,
        _.get_foo3(),
        _.set_foo3(_a)
      )
  BOOST_MIRROR_REG_CLASS_MEM_VARS_END
    float someFunc(int);
    BOOST_MIRROR_REG_MEM_FUNCTION_BEGIN(public, _, float, someFunc, someFuncI)
      BOOST_MIRROR_REG_MEM_FUNCTION_PARAM(int, i)
    BOOST_MIRROR_REG_MEM_FUNCTION_END(someFunc, someFuncI)
BOOST_MIRROR_REG_CLASS_END

And it has things to handle type conversions supported and much more.
The docs are at:  http://kifri.fri.uniza.sk/~chochlik/mirror-lib/html/
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Jon Watte | 5 Jul 2010 20:48
Picon
Gravatar

Re: The effect of cache on performance

Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.
 
Do you really think there's such a thing as "right," unless you're talking directly observable physical phenomena?
 
Sincerely,
 
jw


--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.



On Thu, Jul 1, 2010 at 1:12 AM, Richard Fabian <raspo1 <at> gmail.com> wrote:
Any development approach where you don't consider the effect of the cache is going to have inferior performance to one that either implicitly, or explicitly, takes advantage of the cache.

I do feel like we've been taught a lot of really good coding techniques that have ignored this issue. It doesn't mean that the code oriented techniques aren't good, for fast memory hardware our coding style and experience is invaluable.


On 1 July 2010 06:12, Richard <legalize <at> xmission.com> wrote:
I stumbled across this today and found it an interesting read.
<http://queue.acm.org/detail.cfm?id=1814327>

It relates to our "virtual function calls are bad!"[*] discussion
earlier.

[*] they're not really bad, its cache misses that are bad.
--
"The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download
 <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/>

     Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com



--
fabs();
Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com


_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Jon Watte | 5 Jul 2010 20:49
Picon
Gravatar

Re: The effect of cache on performance

Do you really think there's such a thing as "right," unless you're talking directly observable physical phenomena?
 
Aaand that was supposed to be reply to Richard only. Please let's not have a metaphysical discussion on this list, OK? :-)
 
Sincerely,
 
jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.



On Mon, Jul 5, 2010 at 11:48 AM, Jon Watte <jwatte <at> gmail.com> wrote:
Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.
 
Do you really think there's such a thing as "right," unless you're talking directly observable physical phenomena?
 
Sincerely,
 
jw


--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.



On Thu, Jul 1, 2010 at 1:12 AM, Richard Fabian <raspo1 <at> gmail.com> wrote:
Any development approach where you don't consider the effect of the cache is going to have inferior performance to one that either implicitly, or explicitly, takes advantage of the cache.

I do feel like we've been taught a lot of really good coding techniques that have ignored this issue. It doesn't mean that the code oriented techniques aren't good, for fast memory hardware our coding style and experience is invaluable.


On 1 July 2010 06:12, Richard <legalize <at> xmission.com> wrote:
I stumbled across this today and found it an interesting read.
<http://queue.acm.org/detail.cfm?id=1814327>

It relates to our "virtual function calls are bad!"[*] discussion
earlier.

[*] they're not really bad, its cache misses that are bad.
--
"The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download
 <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/>

     Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com



--
fabs();
Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com



_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Tommy Brett | 5 Jul 2010 21:14
Picon

Re: The effect of cache on performance

If a cache miss happens in a program and no profiler is there to see it, does it really happen?

On Mon, Jul 5, 2010 at 2:49 PM, Jon Watte <jwatte <at> gmail.com> wrote:
Do you really think there's such a thing as "right," unless you're talking directly observable physical phenomena?
 
Aaand that was supposed to be reply to Richard only. Please let's not have a metaphysical discussion on this list, OK? :-)
 
Sincerely,
 
jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.



On Mon, Jul 5, 2010 at 11:48 AM, Jon Watte <jwatte <at> gmail.com> wrote:
Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.
 
Do you really think there's such a thing as "right," unless you're talking directly observable physical phenomena?
 
Sincerely,
 
jw


--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.



On Thu, Jul 1, 2010 at 1:12 AM, Richard Fabian <raspo1 <at> gmail.com> wrote:
Any development approach where you don't consider the effect of the cache is going to have inferior performance to one that either implicitly, or explicitly, takes advantage of the cache.

I do feel like we've been taught a lot of really good coding techniques that have ignored this issue. It doesn't mean that the code oriented techniques aren't good, for fast memory hardware our coding style and experience is invaluable.


On 1 July 2010 06:12, Richard <legalize <at> xmission.com> wrote:
I stumbled across this today and found it an interesting read.
<http://queue.acm.org/detail.cfm?id=1814327>

It relates to our "virtual function calls are bad!"[*] discussion
earlier.

[*] they're not really bad, its cache misses that are bad.
--
"The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download
 <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/>

     Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com



--
fabs();
Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com




_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com


_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Fabian Giesen | 6 Jul 2010 03:36
Picon

Re: The effect of cache on performance

On 05.07.2010 12:14, Tommy Brett wrote:
> If a cache miss happens in a program and no profiler is there to see it,
> does it really happen?

Unfortunately, the answer is YES.

One of the other cores told me. They're always snooping the bus because 
they like to gloat when someone misses the cache... sneaky bastards.

-Fabian
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Blair Holloway | 8 Jul 2010 04:50

Breaking matchmaking deadlocks

Rather than taking the typical "join session/host session" approach with our upcoming title, we're going to adopt a matchmaking solution - the user selects the "find players" option, and under the covers the game deals with creating and joining as necessary.


We've been examining the matchmaking system described in "E Pluribus Unum: Matchmaking in HALO 3"[1], and decided to take a similar approach -- when matchmaking begins, a "gatherer" task hosts a session, and waits for players to connect to it, whilst a "hunter" task enumerates a list of sessions and tries to join each in turn.

Since these tasks happen simultaneously, it's possible to end up in a quasi-deadlock -- the hunter task from machine A can connect to the gatherer's session on machine B, whilst machine B's hunter simultaneously connects to machine A's gatherer; both machines would be simultaneously hosting two sessions, and each machine would be participating in both.

The easiest solution to this is perhaps to avoid the "deadlock" in the first place, and not simultaneously search and host. Indeed, the system described in Halo 3 seems to randomly decide at the start of matchmaking whether a machine is a hunter or a gatherer, and simply sticks to that choice until a timeout occur.

However, Halo has the advantage of a huge player base to make this work; we're expecting a few orders-of-magnitude less players, and are worried that when, say only a few tens of people are online at any given time, only gathering or hunting will make the matchmaking experience slow for the user. Therefore, we'd like to both gather and hunt at the same time, and try to avoid the deadlocks and "break" them when they occur -- i.e. when detecting simultaneous connections, choose one session to destroy, whilst keeping the other.

Does anyone have any suggestions for how to break these "deadlocks"?

Cheers,

- Blair

_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Conor Stokes | 8 Jul 2010 07:14
Picon
Favicon

Re: Breaking matchmaking deadlocks

Maintain a shared set of connections (in a hash or something) for both in-coming and out-going (hunting and gathering), protected by a lock and keyed by user. Then don't allow inserts/drop the connection into the shared set if you find a connection already there. It's a small relatively constant time operation and you should be able to set it up for the right order of operations such that you won't end up with an inconsistent set between players. 

Cheers,
Conor 

From: Blair Holloway <thynameisblair <at> chaosandcode.com>
To: sweng-gamedev <at> midnightryder.com
Sent: Thu, 8 July, 2010 10:50:25 AM
Subject: [Sweng-Gamedev] Breaking matchmaking deadlocks

Rather than taking the typical "join session/host session" approach with our upcoming title, we're going to adopt a matchmaking solution - the user selects the "find players" option, and under the covers the game deals with creating and joining as necessary.

We've been examining the matchmaking system described in "E Pluribus Unum: Matchmaking in HALO 3"[1], and decided to take a similar approach -- when matchmaking begins, a "gatherer" task hosts a session, and waits for players to connect to it, whilst a "hunter" task enumerates a list of sessions and tries to join each in turn.

Since these tasks happen simultaneously, it's possible to end up in a quasi-deadlock -- the hunter task from machine A can connect to the gatherer's session on machine B, whilst machine B's hunter simultaneously connects to machine A's gatherer; both machines would be simultaneously hosting two sessions, and each machine would be participating in both.

The easiest solution to this is perhaps to avoid the "deadlock" in the first place, and not simultaneously search and host. Indeed, the system described in Halo 3 seems to randomly decide at the start of matchmaking whether a machine is a hunter or a gatherer, and simply sticks to that choice until a timeout occur.

However, Halo has the advantage of a huge player base to make this work; we're expecting a few orders-of-magnitude less players, and are worried that when, say only a few tens of people are online at any given time, only gathering or hunting will make the matchmaking experience slow for the user. Therefore, we'd like to both gather and hunt at the same time, and try to avoid the deadlocks and "break" them when they occur -- i.e. when detecting simultaneous connections, choose one session to destroy, whilst keeping the other.

Does anyone have any suggestions for how to break these "deadlocks"?

Cheers,

- Blair


 
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Gmane