Jump to content
  • Advertisement
  • 07/15/14 10:21 PM
    Sign in to follow this  

    Abusing the Linker to Minimize Compilation Time

    General and Gameplay Programming

    fastcall22

    Abstract

    In this article, I will describe a technique that reduces coupling between an object that provides access to many types of objects ("the provider") and its users by moving compile-time dependencies to link-time. In doing so, we can reduce the amount of unnecessary compiling of the provider's dependencies whenever the provider is changed. I will then explore the benefits and costs to such a design.

    The Problem

    Typically in a game, a provider object is needed to expose a variety of services and objects to many parts of the game, much like a heart pumps blood throughout the body. This provider object is a sort of "context object", which is setup with the current state of the game and exposes other useful objects. Such a class could look something like listing 1, and an example of use could look something like listing 2. // // Listing 1: // ServiceContext.h #pragma once // Dependencies class Game; class World; class RenderService; class ResourceService; class PathfindingService; class PhysicsService; class LogService; // ServiceContext // Provides access to a variety of objects class ServiceContext { public: Game* const game; World* const world; RenderService* const render; PathfindingService* const path; PhysicsService* const physics; AudioService* const audio; LogService* const log; }; Listing 1: The definition of a sample context object // // Listing 2: // Foobar.cpp #include "Foobar.h" #include "ServiceContext.h" #include "PathService.h" #include "LogService.h" void Foobar::frobnicate( ServiceContext& ctx ) { if ( !condition() ) return; current_path = ctx.path->evaluate(position, target->position); if ( !current_path ) ctx->log("Warning","No path found!"); } Listing 2: An example usage of the sample context object The ServiceContext is the blood of the program, and many objects depend on it. If a new service is added to ServiceContext or ServiceContext is changed in any way, then all of its dependents will be recompiled, regardless if the dependent uses the new service. See figure 1.
    figure1-final_480px.png Figure 1: Recompilations needed when adding a service to the provider object
    To reduce these unnecessary recompilations, we can use (abuse) the linker to hide the dependencies.

    The Solution

    We can hide the dependencies by moving compile-time dependencies to link-time dependencies. With templates, we can write a generic get function and supply specialized definitions in its translation unit. // // Listing 3: // ServiceContext.h #pragma once // Dependencies struct ServiceContextImpl; // ServiceContext // Provides access to a variety of objects class ServiceContext { public: // Constructors ServiceContext( ServiceContextImpl& p ); public: // Methods template T* get() const; private: // Members ServiceContextImpl& impl; }; // // ServiceContextImpl.h #pragma once // Dependencies class Game; class World; class RenderService; class ResourceService; class PathfindingService; class PhysicsService; class LogService; // ServiceContextImpl // Exposes the objects to ServiceContext // Be sure to update ServiceContext.cpp whenever this definition changes! struct ServiceContextImpl { Game* const game; World* const world; RenderService* const render; PathfindingService* const path; PhysicsService* const physics; AudioService* const audio; LogService* const log; }; Listing 3: The declarations of the two new classes // // Listing 4: // ServiceContext.cpp #include "ServiceContext.h" #include "ServiceContextImpl.h" ServiceContext::ServiceContext( ServiceContextImpl& p ) : impl(p) { } // Expose impl by providing the specializations for ServiceContext::get template<> Game* ServiceContext::get() { return impl.game; } // ... or use a macro #define SERVICECONTEXT_GET( type, name ) \ template<> \ type* ServiceContext::get() const { \ return impl.name; \ } SERVICECONTEXT_GET( World, world ); SERVICECONTEXT_GET( RenderService, render ); SERVICECONTEXT_GET( PathfindingService, path ); SERVICECONTEXT_GET( PhysicsService, physics ); SERVICECONTEXT_GET( AudioService, audio ); SERVICECONTEXT_GET( LogService, log ); Listing 4: The new ServiceContext definition In listing 3, we have delegated the volatile definition of ServiceContext to a new class, ServiceContextImpl. In addition, we now have a generic get member function which can generate member function declarations for every type of service we wish to provide. In listing 4, we provide the get definitions for every member of ServiceContextImpl. The definitions are provided to the linker at link-time, which are then linked to the modules that use the ServiceContext. // // Listing 5: // Foobar.cpp #pragma once #include "Foobar.h" #include "ServiceContext.h" #include "PathService.h" #include "LogService.h" void Foobar::frobnicate( ServiceContext& ctx ) { if ( !condition() ) return; current_path = ctx.get()->evaluate(position, target->position); if ( !current_path ) ctx.get()->log("Warning","No path found!"); } Listing 5: The Foobar implementation using the new ServiceContext With this design, ServiceContext can remain unchanged and all changes to its implementation are only known to those objects that setup the ServiceContext object. See figure 2.
    figure2-final_480px.png Figure 2: Adding new services to ServiceContextImpl now has minimal impact on ServiceContext's dependants
    When a new service is added, Game and ServiceContextImpl are recompiled into new modules, and the linker relinks dependencies with the new definitions. If all went well, this relinking should cost less than recompiling each dependency.

    The Caveats

    There are a few considerations to make before using this solution:
    1. The solution hinges on the linker's support for "whole program optimization" and can inline the ServiceContext's get definitions at link-time. If this optimization is supported, then there is no additional cost to using this solution over the traditional approach. MSVC and GCC have support for this optimization.
    2. It is assumed that ServiceContext is changed often during development, though usually during early development. It can be argued that such a complicated system is not needed after a few iterations of ServiceContext.
    3. It is assumed that the compiling time greatly outweighs linking time. This solution may not be appropriate for larger projects.
    4. The solution favors cleverness over readability. There is a increase in complexity with such a solution, and it could be argued that the complexity is not worth the marginal savings in compiling time. This solution may not be appropriate if the project has multiple developers.
    5. The solution does not offer any advantage in Unity builds.

    Conclusion

    While this solution does reduce unnecessary recompilations, it does add complexity to the project. Depending on the size of the project, the solution should grant a small to medium sized project with decreased compilation time.


      Report Article
    Sign in to follow this  


    User Feedback


    I have run into this same issue in my code before, and tried to think of a good solution. I like your approach. I agree on a large project it may not have the most benefit. I worked on a game with a large team where the compiles were distributed, but linking was local which usually took a big chunk of time. On my personal project, though, this would work great. Will try it out. Thanks!

    Share this comment


    Link to comment
    Share on other sites

    ServiceContext is a bad design example, terrible dependencies management. smile.png.

    Exposing these many dependencies through single one is a bad design.

    There should be no single component in any game or engine which should need that many of them at single time.

     

     

     

    3. It is assumed that the compiling time greatly outweighs linking time. This solution may not be appropriate for larger projects.

     

    It is not even true for smaller projects with any modern compiler + pch.

    The reason is that more separate objs means doing same work twice(getting symbols out and fulfilling dependencies). One during compilation and then same during linking stage. 

    Share this comment


    Link to comment
    Share on other sites
    Fair enough. I agree that an alternative design would be better. I won't even pretend to advocate that this is a good design.

    Thanks for your feedback.

    Share this comment


    Link to comment
    Share on other sites
    I feel like the main disadvantage (after 4.) is that your ".get" method now needs to be parameterized on a particular type that may not be obvious. I don't want to have to remember that the type was "PathfindingService" and not "PathfinderService"--and heaven forbid what happens should I want to change any of these names. Plus, Intellisense-type features become a lot less helpful (it can't suggest reasonable types to put in the template in the same way it could suggest reasonable fields to dereference).

    All that said, I have used something similar in my projects myself. It's interesting that you cast it as a compile-time versus link-time tradeoff; my main application was abstraction.

    If you're feeling especially devilish, you can replace your implementation class with a std::vector of void* (or of some base type). That will let you only have two files (which IMO is much more clear than having three or four to fill one semantic purpose).

    Share this comment


    Link to comment
    Share on other sites

    Regardless of whether the 'service provider' / 'context object' is a good pattern, this is still a neat trick :D

    Share this comment


    Link to comment
    Share on other sites

    Intellisense-type features become a lot less helpful

    I agree. However, you might still be able to browse [tt]ctx.impl[/tt] for names and types. It's not as intuitive, but it might be possible.
     

    All that said, I have used something similar in my projects myself. It's interesting that you cast it as a compile-time versus link-time tradeoff; my main application was abstraction.

    Do you think the article would be better if it were structured around "abstraction" rather than "reducing compile time"? This is my first article and I may have constructed my argument improperly.
     

    If you're feeling especially devilish, you can replace your implementation class with a std::vector of void* (or of some base type). That will let you only have two files (which IMO is much more clear than having three or four to fill one semantic purpose).


    In this approach, you'd lose type safety, Intellisense information, and you'd have to carefully manage how the vector is setup. Though, you could mitigate some of this cost with using the base type and dynamic cast in debug mode or a static_assert. You'd also have another level of indirection with some heap memory, but this can also be mitigated with a raw pointer-to an array on the stack (lifetime constrained to the owner's)...

    Share this comment


    Link to comment
    Share on other sites

    Service Locator is an antipattern. Despite it may seems a good idea immediatly, it expose the whole code base to unexpected dependencies (the real problem is that you still have to pass the context around complicating a little extra your application: you still need to warry about "entry point"). This is not a real issue if you are working on your own little project (well it may become an issue anyway). Usually to solve problems of "context" you need the help of a Depdency Injection framework, a simple one is Infector++ (C++11 only), there are more complex frameworks that allows multiple context (never needed personally but is possible) like hypodermic. Using such framework requires a little more work at first but saves many time later. The really good point is that you separate object creation (glue code) from application logic (you don't need to think where to create a service, you just need to know dependencies). You istantiate objects from factories and everything those objects needs is added on the fly. There's some overhead (at initialization time), but you gain in project maintenability and flexibility and also you can later decide to use a custom allocator to speed up things (adding custom allocation extremily more easy with helps of such frameworks)

    When you have concrete implementations on one side, interfaces on the other side and no need to warry about "when and where" objects will be created you will find that compilation will be also greatly reduced (the longest to compile source file will be the CompositionRoot, wich you can split in multiple methods to reduce compile time anyway) allowing quick iteration more efficiently (we are speaking about human performance, not CPU performance)

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!