One Weird Trick to Write Better Code

In search of the One Weird Trick

I'll talk about a lot of tricks...

But we're looking for the One Weird Trick to rule them all

Start at the beginning

We've all been here

var x = 314;
var y = 8;
var prevy= 1;
var prevx= 1;
var prevsw= 0;
var row= 304;
var endrow= 142;
var sword= 296;
var yrow = 0;
var yendrow = 186;
var I = 0;
var e = 0;
var counter = 0;
var found = 0;
var esword = 26;
var eprevsw = 8;
var bluehealth = 40;
var redhealth = 40;
var n = 0;
var you = 'ninja';
var bullet = 'sword';
var enemy = 'enemy';
var ebullet = 'enemysword';
var besieged = 0;
var siegecount = 0;
var esiegecount = 0;
var ebesieged = 0;
var healthcount = 0;
var player = 0;
var starcount = 0;
var infortress = false;
var prevyou = you;
var einfortress = false;
var prevenemy = enemy;
var previmg = "";
var prevbullet= "";
var eprevbullet= "";
var randnum = 0;
var randnum2 = 0;
var randnum3 = 0;
var randnum4 = 0;
var buildcount = 0;
var characters = new Array(4);
characters = ['ninja','tank','heli','builder'];
var bullets = new Array(3);
bullets = ['sword','bullet','5cal','sword'];
var echaracters = new Array(3);
echaracters = ['enemy','tank2','eheli','ebuilder'];
var ebullets = new Array(3);
ebullets = ['enemysword','bullet2','e5cal','enemysword'];
var health = new Array(4);
health = [40,30,20,10];
var prevorb = 0;
var prevnum = 0;
					

Trick #1

Don't use globals

Trick #2: object-oriented to the rescue!

class Ninja
{
	int x, y;
	int previousX, previousY;
	int health = 100;
}

class Sword
{
	int x, y;
	int previousX, previousY;
	int sharpness = 9000;
}
					

We can even do this

class Movable
{
	int x, y;
	int previousX, previousY;
}

class Ninja : public Movable
{
	int health = 100;
}

class Sword : public Movable
{
	int sharpness = 9000;
}
					

Classic game code

Doom 3 source - github.com/id-Software/DOOM-3-BFG

• idClass
  • idEntity
    • idAnimatedEntity
      • idWeapon
      • idAFEntity_Base
        • idAFEntity_ClawFourFingers
        • idAFEntity_Vehicle
          • idAFEntity_VehicleFourWheels
          • idAFEntity_VehicleSixWheels
        • idAFEntity_Gibbable
          • idAFEntity_WithAttachedHead
          • idActor
            • idPlayer
            • idAI

Problem

"The player is now a car"

• idClass
  • idEntity
    • idAnimatedEntity
      • idWeapon
      • idAFEntity_Base
        • idAFEntity_ClawFourFingers
        • idAFEntity_Vehicle
          • idAFEntity_VehicleFourWheels <------------
          • idAFEntity_VehicleSixWheels
        • idAFEntity_Gibbable
          • idAFEntity_WithAttachedHead
          • idActor
            • idPlayer <------------
            • idAI

More subtle but dangerous problem

"Some code needs to go in both VehicleFourWheels and idPlayer"

• idClass
  • idEntity
    • idAnimatedEntity
      • idWeapon
      • idAFEntity_Base <------------------ right here. perfect.
        • idAFEntity_ClawFourFingers
        • idAFEntity_Vehicle
          • idAFEntity_VehicleFourWheels <------------
          • idAFEntity_VehicleSixWheels
        • idAFEntity_Gibbable
          • idAFEntity_WithAttachedHead
          • idActor
            • idPlayer <------------
            • idAI

The terrible, logical conclusion

class idEntity : public idClass {
public:
	static const int		MAX_PVS_AREAS = 4;
	static const uint32		INVALID_PREDICTION_KEY = 0xFFFFFFFF;

	int						entityNumber;			// index into the entity list
	int						entityDefNumber;		// index into the entity def list

	idLinkList<idEntity>	spawnNode;				// for being linked into spawnedEntities list
	idLinkList<idEntity>	activeNode;				// for being linked into activeEntities list
	idLinkList<idEntity>	aimAssistNode;			// linked into gameLocal.aimAssistEntities

	idLinkList<idEntity>	snapshotNode;			// for being linked into snapshotEntities list
	int						snapshotChanged;		// used to detect snapshot state changes
	int						snapshotBits;			// number of bits this entity occupied in the last snapshot
	bool					snapshotStale;			// Set to true if this entity is considered stale in the snapshot

	idStr					name;					// name of entity
	idDict					spawnArgs;				// key/value pairs used to spawn and initialize entity
	idScriptObject			scriptObject;			// contains all script defined data for this entity

	int						thinkFlags;				// TH_? flags
	int						dormantStart;			// time that the entity was first closed off from player
	bool					cinematic;				// during cinematics, entity will only think if cinematic is set

	renderView_t *			renderView;				// for camera views from this entity
	idEntity *				cameraTarget;			// any remoteRenderMap shaders will use this

	idList< idEntityPtr<idEntity>, TAG_ENTITY >	targets;		// when this entity is activated these entities entity are activated

	int						health;					// FIXME: do all objects really need health?

	struct entityFlags_s {
		bool				notarget			:1;	// if true never attack or target this entity
		bool				noknockback			:1;	// if true no knockback from hits
		bool				takedamage			:1;	// if true this entity can be damaged
		bool				hidden				:1;	// if true this entity is not visible
		bool				bindOrientated		:1;	// if true both the master orientation is used for binding
		bool				solidForTeam		:1;	// if true this entity is considered solid when a physics team mate pushes entities
		bool				forcePhysicsUpdate	:1;	// if true always update from the physics whether the object moved or not
		bool				selected			:1;	// if true the entity is selected for editing
		bool				neverDormant		:1;	// if true the entity never goes dormant
		bool				isDormant			:1;	// if true the entity is dormant
		bool				hasAwakened			:1;	// before a monster has been awakened the first time, use full PVS for dormant instead of area-connected
		bool				networkSync			:1; // if true the entity is synchronized over the network
		bool				grabbed				:1;	// if true object is currently being grabbed
		bool				skipReplication		:1; // don't replicate this entity over the network.
	} fl;

	int						timeGroup;

	bool					noGrab;

	renderEntity_t			xrayEntity;
	qhandle_t				xrayEntityHandle;
	const idDeclSkin *		xraySkin;

	void					DetermineTimeGroup( bool slowmo );

	void					SetGrabbedState( bool grabbed );
	bool					IsGrabbed();

public:
	ABSTRACT_PROTOTYPE( idEntity );

							idEntity();
							~idEntity();

	void					Spawn();

	void					Save( idSaveGame *savefile ) const;
	void					Restore( idRestoreGame *savefile );

	const char *			GetEntityDefName() const;
	void					SetName( const char *name );
	const char *			GetName() const;
	virtual void			UpdateChangeableSpawnArgs( const idDict *source );
	int						GetEntityNumber() const { return entityNumber; }

							// clients generate views based on all the player specific options,
							// cameras have custom code, and everything else just uses the axis orientation
	virtual renderView_t *	GetRenderView();

	// thinking
	virtual void			Think();
	bool					CheckDormant();	// dormant == on the active list, but out of PVS
	virtual	void			DormantBegin();	// called when entity becomes dormant
	virtual	void			DormantEnd();		// called when entity wakes from being dormant
	bool					IsActive() const;
	void					BecomeActive( int flags );
	void					BecomeInactive( int flags );
	void					UpdatePVSAreas( const idVec3 &pos );
	void					BecomeReplicated();

	// visuals
	virtual void			Present();
	virtual renderEntity_t *GetRenderEntity();
	virtual int				GetModelDefHandle();
	virtual void			SetModel( const char *modelname );
	void					SetSkin( const idDeclSkin *skin );
	const idDeclSkin *		GetSkin() const;
	void					SetShaderParm( int parmnum, float value );
	virtual void			SetColor( float red, float green, float blue );
	virtual void			SetColor( const idVec3 &color );
	virtual void			GetColor( idVec3 &out ) const;
	virtual void			SetColor( const idVec4 &color );
	virtual void			GetColor( idVec4 &out ) const;
	virtual void			FreeModelDef();
	virtual void			FreeLightDef();
	virtual void			Hide();
	virtual void			Show();
	bool					IsHidden() const;
	void					UpdateVisuals();
	void					UpdateModel();
	void					UpdateModelTransform();
	virtual void			ProjectOverlay( const idVec3 &origin, const idVec3 &dir, float size, const char *material );
	int						GetNumPVSAreas();
	const int *				GetPVSAreas();
	void					ClearPVSAreas();
	bool					PhysicsTeamInPVS( pvsHandle_t pvsHandle );

	// animation
	virtual bool			UpdateAnimationControllers();
	bool					UpdateRenderEntity( renderEntity_s *renderEntity, const renderView_t *renderView );
	static bool				ModelCallback( renderEntity_s *renderEntity, const renderView_t *renderView );
	virtual idAnimator *	GetAnimator();	// returns animator object used by this entity

	// sound
	virtual bool			CanPlayChatterSounds() const;
	bool					StartSound( const char *soundName, const s_channelType channel, int soundShaderFlags, bool broadcast, int *length );
	bool					StartSoundShader( const idSoundShader *shader, const s_channelType channel, int soundShaderFlags, bool broadcast, int *length );
	void					StopSound( const s_channelType channel, bool broadcast );	// pass SND_CHANNEL_ANY to stop all sounds
	void					SetSoundVolume( float volume );
	void					UpdateSound();
	int						GetListenerId() const;
	idSoundEmitter *		GetSoundEmitter() const;
	void					FreeSoundEmitter( bool immediate );

	// entity binding
	virtual void			PreBind();
	virtual void			PostBind();
	virtual void			PreUnbind();
	virtual void			PostUnbind();
	void					JoinTeam( idEntity *teammember );
	void					Bind( idEntity *master, bool orientated );
	void					BindToJoint( idEntity *master, const char *jointname, bool orientated );
	void					BindToJoint( idEntity *master, jointHandle_t jointnum, bool orientated );
	void					BindToBody( idEntity *master, int bodyId, bool orientated );
	void					Unbind();
	bool					IsBound() const;
	bool					IsBoundTo( idEntity *master ) const;
	idEntity *				GetBindMaster() const;
	jointHandle_t			GetBindJoint() const;
	int						GetBindBody() const;
	idEntity *				GetTeamMaster() const;
	idEntity *				GetNextTeamEntity() const;
	void					ConvertLocalToWorldTransform( idVec3 &offset, idMat3 &axis );
	idVec3					GetLocalVector( const idVec3 &vec ) const;
	idVec3					GetLocalCoordinates( const idVec3 &vec ) const;
	idVec3					GetWorldVector( const idVec3 &vec ) const;
	idVec3					GetWorldCoordinates( const idVec3 &vec ) const;
	bool					GetMasterPosition( idVec3 &masterOrigin, idMat3 &masterAxis ) const;
	void					GetWorldVelocities( idVec3 &linearVelocity, idVec3 &angularVelocity ) const;

	// physics
							// set a new physics object to be used by this entity
	void					SetPhysics( idPhysics *phys );
							// get the physics object used by this entity
	idPhysics *				GetPhysics() const;
							// restore physics pointer for save games
	void					RestorePhysics( idPhysics *phys );
							// run the physics for this entity
	bool					RunPhysics();
							// Interpolates the physics, used on MP clients.
	void					InterpolatePhysics( const float fraction );
							// InterpolatePhysics actually calls evaluate, this version doesn't.
	void					InterpolatePhysicsOnly( const float fraction, bool updateTeam = false );
							// set the origin of the physics object (relative to bindMaster if not NULL)
	void					SetOrigin( const idVec3 &org );
							// set the axis of the physics object (relative to bindMaster if not NULL)
	void					SetAxis( const idMat3 &axis );
							// use angles to set the axis of the physics object (relative to bindMaster if not NULL)
	void					SetAngles( const idAngles &ang );
							// get the floor position underneath the physics object
	bool					GetFloorPos( float max_dist, idVec3 &floorpos ) const;
							// retrieves the transformation going from the physics origin/axis to the visual origin/axis
	virtual bool			GetPhysicsToVisualTransform( idVec3 &origin, idMat3 &axis );
							// retrieves the transformation going from the physics origin/axis to the sound origin/axis
	virtual bool			GetPhysicsToSoundTransform( idVec3 &origin, idMat3 &axis );
							// called from the physics object when colliding, should return true if the physics simulation should stop
	virtual bool			Collide( const trace_t &collision, const idVec3 &velocity );
							// retrieves impact information, 'ent' is the entity retrieving the info
	virtual void			GetImpactInfo( idEntity *ent, int id, const idVec3 &point, impactInfo_t *info );
							// apply an impulse to the physics object, 'ent' is the entity applying the impulse
	virtual void			ApplyImpulse( idEntity *ent, int id, const idVec3 &point, const idVec3 &impulse );
							// add a force to the physics object, 'ent' is the entity adding the force
	virtual void			AddForce( idEntity *ent, int id, const idVec3 &point, const idVec3 &force );
							// activate the physics object, 'ent' is the entity activating this entity
	virtual void			ActivatePhysics( idEntity *ent );
							// returns true if the physics object is at rest
	virtual bool			IsAtRest() const;
							// returns the time the physics object came to rest
	virtual int				GetRestStartTime() const;
							// add a contact entity
	virtual void			AddContactEntity( idEntity *ent );
							// remove a touching entity
	virtual void			RemoveContactEntity( idEntity *ent );

	// damage
							// returns true if this entity can be damaged from the given origin
	virtual bool			CanDamage( const idVec3 &origin, idVec3 &damagePoint ) const;
							// applies damage to this entity
	virtual	void			Damage( idEntity *inflictor, idEntity *attacker, const idVec3 &dir, const char *damageDefName, const float damageScale, const int location );
							// adds a damage effect like overlays, blood, sparks, debris etc.
	virtual void			AddDamageEffect( const trace_t &collision, const idVec3 &velocity, const char *damageDefName );
							// callback function for when another entity received damage from this entity.  damage can be adjusted and returned to the caller.
	virtual void			DamageFeedback( idEntity *victim, idEntity *inflictor, int &damage );
							// notifies this entity that it is in pain
	virtual bool			Pain( idEntity *inflictor, idEntity *attacker, int damage, const idVec3 &dir, int location );
							// notifies this entity that is has been killed
	virtual void			Killed( idEntity *inflictor, idEntity *attacker, int damage, const idVec3 &dir, int location );

	// scripting
	virtual bool			ShouldConstructScriptObjectAtSpawn() const;
	virtual idThread *		ConstructScriptObject();
	virtual void			DeconstructScriptObject();
	void					SetSignal( signalNum_t signalnum, idThread *thread, const function_t *function );
	void					ClearSignal( idThread *thread, signalNum_t signalnum );
	void					ClearSignalThread( signalNum_t signalnum, idThread *thread );
	bool					HasSignal( signalNum_t signalnum ) const;
	void					Signal( signalNum_t signalnum );
	void					SignalEvent( idThread *thread, signalNum_t signalnum );

	// gui
	void					TriggerGuis();
	bool					HandleGuiCommands( idEntity *entityGui, const char *cmds );
	virtual bool			HandleSingleGuiCommand( idEntity *entityGui, idLexer *src );

	// targets
	void					FindTargets();
	void					RemoveNullTargets();
	void					ActivateTargets( idEntity *activator ) const;

	// misc
	virtual void			Teleport( const idVec3 &origin, const idAngles &angles, idEntity *destination );
	bool					TouchTriggers() const;
	idCurve_Spline<idVec3> *GetSpline() const;
	virtual void			ShowEditingDialog();

	enum {
		EVENT_STARTSOUNDSHADER,
		EVENT_STOPSOUNDSHADER,
		EVENT_MAXEVENTS
	};

	// Called on clients in an MP game, does the actual interpolation for the entity.
	// This function will eventually replace ClientPredictionThink completely.
	virtual void			ClientThink( const int curTime, const float fraction, const bool predict );

	virtual void			ClientPredictionThink();
	virtual void			WriteToSnapshot( idBitMsg &msg ) const;
	void					ReadFromSnapshot_Ex( const idBitMsg &msg );
	virtual void			ReadFromSnapshot( const idBitMsg &msg );
	virtual bool			ServerReceiveEvent( int event, int time, const idBitMsg &msg );
	virtual bool			ClientReceiveEvent( int event, int time, const idBitMsg &msg );

	void					WriteBindToSnapshot( idBitMsg &msg ) const;
	void					ReadBindFromSnapshot( const idBitMsg &msg );
	void					WriteColorToSnapshot( idBitMsg &msg ) const;
	void					ReadColorFromSnapshot( const idBitMsg &msg );
	void					WriteGUIToSnapshot( idBitMsg &msg ) const;
	void					ReadGUIFromSnapshot( const idBitMsg &msg );

	void					ServerSendEvent( int eventId, const idBitMsg *msg, bool saveEvent, lobbyUserID_t excluding = lobbyUserID_t() ) const;
	void					ClientSendEvent( int eventId, const idBitMsg *msg ) const;

	void					SetUseClientInterpolation( bool use ) { useClientInterpolation = use; }

	void					SetSkipReplication( const bool skip ) { fl.skipReplication = skip; }
	bool					GetSkipReplication() const { return fl.skipReplication; }
	bool					IsReplicated() const { return  GetEntityNumber() < ENTITYNUM_FIRST_NON_REPLICATED; }

	void					CreateDeltasFromOldOriginAndAxis( const idVec3 & oldOrigin, const idMat3 & oldAxis );
	void					DecayOriginAndAxisDelta();
	uint32					GetPredictedKey() { return predictionKey; }
	void					SetPredictedKey( uint32 key_ ) { predictionKey = key_; }

	void					FlagNewSnapshot();

	idEntity*				GetTeamChain() { return teamChain; }

	// It is only safe to interpolate if this entity has received two snapshots.
	enum interpolationBehavior_t {
		USE_NO_INTERPOLATION,
		USE_LATEST_SNAP_ONLY,
		USE_INTERPOLATION
	};

	interpolationBehavior_t GetInterpolationBehavior() const { return interpolationBehavior; }
	unsigned int			GetNumSnapshotsReceived() const { return snapshotsReceived; }

protected:
	renderEntity_t			renderEntity;						// used to present a model to the renderer
	int						modelDefHandle;						// handle to static renderer model
	refSound_t				refSound;							// used to present sound to the audio engine

	idVec3					GetOriginDelta() const { return originDelta; }
	idMat3					GetAxisDelta() const { return axisDelta; }
	
private:
	idPhysics_Static		defaultPhysicsObj;					// default physics object
	idPhysics *				physics;							// physics used for this entity
	idEntity *				bindMaster;							// entity bound to if unequal NULL
	jointHandle_t			bindJoint;							// joint bound to if unequal INVALID_JOINT
	int						bindBody;							// body bound to if unequal -1
	idEntity *				teamMaster;							// master of the physics team
	idEntity *				teamChain;							// next entity in physics team
	bool					useClientInterpolation;				// disables interpolation for some objects (handy for weapon world models)
	int						numPVSAreas;						// number of renderer areas the entity covers
	int						PVSAreas[MAX_PVS_AREAS];			// numbers of the renderer areas the entity covers

	signalList_t *			signals;

	int						mpGUIState;							// local cache to avoid systematic SetStateInt

	uint32					predictionKey;						// Unique key used to sync predicted ents (projectiles) in MP.

	// Delta values that are set when the server or client disagree on where the render model should be. If this happens,
	// they resolve it through DecayOriginAndAxisDelta()
	idVec3					originDelta;
	idMat3					axisDelta;

	interpolationBehavior_t	interpolationBehavior;	
	unsigned int			snapshotsReceived;

private:
	void					FixupLocalizedStrings();

	bool					DoDormantTests();				// dormant == on the active list, but out of PVS

	// physics
							// initialize the default physics
	void					InitDefaultPhysics( const idVec3 &origin, const idMat3 &axis );
							// update visual position from the physics
	void					UpdateFromPhysics( bool moveBack );
							// get physics timestep
	virtual int				GetPhysicsTimeStep() const;

	// entity binding
	bool					InitBind( idEntity *master );		// initialize an entity binding
	void					FinishBind();					// finish an entity binding
	void					RemoveBinds();				// deletes any entities bound to this object
	void					QuitTeam();					// leave the current team

	void					UpdatePVSAreas();

	// events
	void					Event_GetName();
	void					Event_SetName( const char *name );
	void					Event_FindTargets();
	void					Event_ActivateTargets( idEntity *activator );
	void					Event_NumTargets();
	void					Event_GetTarget( float index );
	void					Event_RandomTarget( const char *ignore );
	void					Event_Bind( idEntity *master );
	void					Event_BindPosition( idEntity *master );
	void					Event_BindToJoint( idEntity *master, const char *jointname, float orientated );
	void					Event_Unbind();
	void					Event_RemoveBinds();
	void					Event_SpawnBind();
	void					Event_SetOwner( idEntity *owner );
	void					Event_SetModel( const char *modelname );
	void					Event_SetSkin( const char *skinname );
	void					Event_GetShaderParm( int parmnum );
	void					Event_SetShaderParm( int parmnum, float value );
	void					Event_SetShaderParms( float parm0, float parm1, float parm2, float parm3 );
	void					Event_SetColor( float red, float green, float blue );
	void					Event_GetColor();
	void					Event_IsHidden();
	void					Event_Hide();
	void					Event_Show();
	void					Event_CacheSoundShader( const char *soundName );
	void					Event_StartSoundShader( const char *soundName, int channel );
	void					Event_StopSound( int channel, int netSync );
	void					Event_StartSound( const char *soundName, int channel, int netSync );
	void					Event_FadeSound( int channel, float to, float over );
	void					Event_GetWorldOrigin();
	void					Event_SetWorldOrigin( idVec3 const &org );
	void					Event_GetOrigin();
	void					Event_SetOrigin( const idVec3 &org );
	void					Event_GetAngles();
	void					Event_SetAngles( const idAngles &ang );
	void					Event_SetLinearVelocity( const idVec3 &velocity );
	void					Event_GetLinearVelocity();
	void					Event_SetAngularVelocity( const idVec3 &velocity );
	void					Event_GetAngularVelocity();
	void					Event_SetSize( const idVec3 &mins, const idVec3 &maxs );
	void					Event_GetSize();
	void					Event_GetMins();
	void					Event_GetMaxs();
	void					Event_Touches( idEntity *ent );
	void					Event_SetGuiParm( const char *key, const char *val );
	void					Event_SetGuiFloat( const char *key, float f );
	void					Event_GetNextKey( const char *prefix, const char *lastMatch );
	void					Event_SetKey( const char *key, const char *value );
	void					Event_GetKey( const char *key );
	void					Event_GetIntKey( const char *key );
	void					Event_GetFloatKey( const char *key );
	void					Event_GetVectorKey( const char *key );
	void					Event_GetEntityKey( const char *key );
	void					Event_RestorePosition();
	void					Event_UpdateCameraTarget();
	void					Event_DistanceTo( idEntity *ent );
	void					Event_DistanceToPoint( const idVec3 &point );
	void					Event_StartFx( const char *fx );
	void					Event_WaitFrame();
	void					Event_Wait( float time );
	void					Event_HasFunction( const char *name );
	void					Event_CallFunction( const char *name );
	void					Event_SetNeverDormant( int enable );
	void					Event_SetGui( int guiNum, const char *guiName);
	void					Event_PrecacheGui( const char *guiName );
	void					Event_GetGuiParm(int guiNum, const char *key);
	void					Event_GetGuiParmFloat(int guiNum, const char *key);
	void					Event_GuiNamedEvent(int guiNum, const char *event);
};
					

Unity to the rescue

Revised structure

• idPlayer
  • idTransform
  • idHealth
  • idAnimatedModel
  • idAnimator
  • idRigidBody
  • idBipedalCharacterController
  • idPlayerController
• idAFEntity_VehicleFourWheels
  • idTransform
  • idAnimatedModel
  • idRigidBody
  • idFourWheelController
• ...

Trick #3

In general, favor composition over inheritance

Why do we avoid globals (trick #1)?
Why is OOP better (trick #2)?
Why is composition even better (trick #3)?

Let's talk about performance

Which function is slower?

double a(double x)
{
	return Math.sqrt(x);
}

static double[] data;
double b(int x)
{
	return data[x];
}
					

Hopefully both get compiled into roughly one instruction each

a = some sort of sqrt instruction

b = some sort of load instruction

Instruction latency

Where's the data?

L1

L2/sqrtps

L3

RAM

Trick #4

Think about cache for huge performance gains

The One Weird Trick

Data first, not code first

Data-Oriented Design

Why should we avoid globals in certain cases?

(trick #1)

Data is not organized correctly

Why does object-oriented programming help?

(trick #2)

It helps you organize your data

Why is composition even better than OOP?

(trick #3)

It helps you organize even better!

Why does my code run faster when I line up data in memory?

(trick #4)

Even your CPU likes it when you organize your data better

Let's compare OOP and DOD

OOP encapsulation

They're all interconnected

System-Level Encapsulation

"But OOP helps us better model the world!"

Steve Yegge's Kingdom of Nouns

• Service
• Manager
• Provider
• Factory

Example: messaging system

• Should a Message object send() itself?
• Or should a Endpoint object send() it?
• Or should a Connection object transmit() it?
• Do we need a ConnectionFactory?

Made-up problems

What you should be asking

• How large are the messages?
• How often are we sending them?

Example: Doom 3

Let's look at Doom 3's update function

for ( idEntity* ent = activeEntities.Next();
       ent != NULL;
       ent = ent->activeNode.Next() )
{
       if ( g_cinematic.GetBool() && inCinematic && !ent->cinematic )
       {
               ent->GetPhysics()->UpdateTime( time );
               continue;
       }
       timer_singlethink.Clear();
       timer_singlethink.Start();
       RunEntityThink( *ent, cmdMgr );
       timer_singlethink.Stop();
       ms = timer_singlethink.Milliseconds();
       if ( ms >= g_timeentities.GetFloat() )
               Printf( "%d: entity '%s': %.1f ms\n", time, ent->name.c_str(), ms );
       num++;
}
					

Looks pretty clean and generic

Questions

• What is executing?
• In what order is it executing?
• Where is the data stored in memory?
• How would you parallelize this?

Compare to this

for (int i = 0; i < rigid_bodies.length; i++)
       rigid_bodies[i].update();

for (int i = 0; i < ai_controllers.length; i++)
       ai_controllers[i].update();

// etc...
					

Takeaway

1. Data first, not code first.
2. Separate behavior and state.
3. Don't instinctively reach for OOP for every problem.

Disclaimers

• Objects are still useful.
• Use the right tool for the right job.
• Hard and fast rules do not exist.

Thank you!

• Slides
  etodd.github.io/one-weird-trick
• Article
  etodd.io/2015/09/28/one-weird-trick-better-code
• Mike Acton - Data-Oriented Design
  youtube.com/watch?v=rX0ItVEVjHc
• Brian Will - Object-Oriented Programming is Bad
  youtube.com/watch?v=QM1iUe6IofM
• Casey Muratori - Semantic Compression
  mollyrocket.com/casey/stream_0019.html