Tuesday, June 16, 2015

Asset management in a real time 3D engine in Haskell

Foreword

In a real time rendering system, it’s not uncommon finding constructs about assets. One famous construct is the resource manager. A resource manager is responsible of several tasks, among:

  • providing a simple interface to load objects from disk (1) ;
  • ensuring we don’t try to load the same object twice (2) ;
  • resolving dependencies between resources (3).

The first point is obvious, but the two others are less intuitive. (2) is important when the user might try to load the same object several times – for instance, a car model, or a character or a weapon. The most known strategy to prevent such a situation from happening is by using a software cache.

A software cache – let’s just say cache – is an opaque object that loads the object on the first request, then just returns that object for future same requests. For instance, consider the following requests and the corresponding cache behavior:

  1. load "wood.png" -> not cached ; loading ; return
  2. load "grass.png" -> not cached ; loading ; return
  3. load "wood.png" -> cached ; return
  4. load "metal.png" -> not cached ; loading ; return
  5. load "metal.png" -> cached ; return
  6. etc.

That behavior is very nice because it will spare a lot of computations and memory space.

(3) is about dependencies. For instance, when you load a car model, you might need to load its textures as well. Well, not really load. Consider the following:

  1. load "car.mesh" -> not cached
    1. load "metal_car.png" -> not cached ; loading ; return
    2. loading ; return
  2. load "metal_car.png" -> cached ; return
  3. load "other_car.mesh" -> not cached
    1. load "metal_car.png" -> cached ; return
    2. return
  4. load "car.mesh" -> cached ; return

You got the idea. (3) needs (2) to be efficient.

Possible implementations

Singleton

In imperative languages and especially in those that support template and/or generics, people tend to implement the cache system with an ugly design pattern – which is actually an anti design pattern : singleton. Each type of resource is assigned a manager by using a template parameter, and then if a manager needs to load a dependency, it just has to reference the corresponding manager by stating the type in the template parameter :

Model & getResource<Model>(std::string const &name) {
  Texture &dependency = getResource<Texture>(...);
  ...
}

That way of doing might sound great, but eh, singletons are just global variables with a unicity constraint. We don’t want that.

Explicit pure store

We can use an explicit store object. That is, some kind of map. For instance, the store that holds textures would have a type like (in Haskell):

textureStore :: Map String Texture

A model store would have the following type:

modelStore :: Map String Model

And each stores is assigned a function; loadTexture, loadModel, and so on.

There are several drawbacks if we go that way. First, we have to carry all stores when using their functions. Some functions might need other stuff in order to resolve dependencies. Secondly, because of explicit state, we need to manually accumulate state! A loading function would have such a following type:

loadTexture :: Map String Texture -> String -> m (Texture,Map String Texture)

That will expose a lot of boilerplate to the user, and we don’t want that.

Implicit pure store

We can enhance the explicit store by putting it into some kind of context; for instance, in MonadState. We can then write loadTexture to make it nicer to use:

loadTexture :: (MonadState (Map String Texture) m,...)
            => String
            -> m Texture

There is a problem with that. What happens when we add more types? For instance if we want to handle textures and models? MonadState has a type family constraint that forbids two instances for the pair s m. The following is not allowed and will raise a compiler error:

instance MonadState (Map String Texture) MyState where
  ...

instance MonadState (Map String Model) MyState where
  ...

The solution to that problem is to have the carried state a polymorphic type and use typeclass constraint to extract and modify the map we want:

class HasMap a s where
  extractMap :: s -> Map String a
  modifyMap :: (Map String a -> Map String a) -> s -> s

With that, we can do something like this:

loadTexture :: (MonadState s m,HasMap Texture s,...)
            => String
            -> m Texture

loadModel :: (MonadState s m,HasMap Texture s,HasMap Model s,...)
          => String
          -> m Model

However, we hit a new issue here. What are s and m? Well, m doesn’t really matter. For simplicity, let’s state we’re using a monad transformer; that is, we use StateT s m as monad.

We still need s. The problem is that s has to be provided by the user. Worse, they have to implement all instances we need so that the loading functions may work. Less boilerplate than the explicit store solution, but still a lot of boilerplate. Imagine you provide a type for s, like Cache. Expending the cache to support new types – like user-defined ones – will be more extra boilerplate to write.

Closures

The solution I use in my engine might not be the perfect solution. It’s not referentially transparent, an important concept in Haskell. However, Haskell is not designed to be used in convenient situations only. We’re hitting a problematic situation. We need to make a compromise between elegance and simplicity.

The solution required the use of closures. If you don’t know what a closure is, you should check out the wikipedia page for a first shot.

The idea is that our loading functions will perform some IO operations to load objects. Why not putting the cache directly in that function? We’d have a function with an opaque and invisible associated state. Consider the following:

type ResourceMap a = Map String a

getTextureManager :: (MonadIO m,...)
                  => m (String -> m Texture)
getTextureManager = do
  ref <- newIORef empty
  pure $ \name -> do
    -- we can use the ref ResourceMap to insert / lookup value in the map
    -- thanks to the closure!

That solution is great because now, a manager is just a function. How would you implement getModelManager? Well:

getModelManager :: (MonadIO m,...)
                => (String -> m Texture)
                -> m (String -> m Model)
getModelManager loadTexture = ...

We can then get the loader functions with the following:

loadTexture <- getTextureManager
loadModel <- getModelManager loadTexture

And you just have to pass those functions around. The cool thing is that you can wrap them in a type in your library and provide a function that initializes them all at once – I do that in my engine. Later on, the user can extend the available managers by providing new functions for new types. In my engine, I provide a few functions like mkResourceManager that hides the ResourceMap, providing two functions – one for lookup in the map, one for inserting into the map.

Conclusion

I truly believe that my solution is a good compromise between elegance and ease. It has a lot of advantages:

  • simple to use ;
  • simple to implement; you just have to play around with closures ;
  • dependencies resolving is easy to add and hidden once the functions are generated ;
  • little runtime overhead (due to closures, might be optimized away by the compiler though) ;
  • can be easily extended by the user to support custom/new types ;
  • if correctly used, implementations can replace IORef with TVar or similar objects for thread-safe implementations ;
  • several replicated functions mean several stores (can be useful in certain cases).

The huge drawback I see in that solution is its opacity. There’s also no way to query the state of each cache. Such a feature could be added by proving a new function, for instance. Same thing for deletion.

I’m one of those Haskellers who love purity. I try to keep my code the purest I can, but there are exceptions, and that cache problem fits that kind of exception.

Feel free to comment, and as always, keep the vibe and happy hacking!

81 comments:

  1. What's wrong with creating a record type with all kinds of resource maps and doing MonadState on top of that ?

    ReplyDelete
    Replies
    1. I had that at first, but it wasn’t flexible enough to me when the user might want to add new resource types.

      Delete
  2. You mean, you want a generic framework for that kind of thing? IMO resource types are always specific to particular application. You could just do state-to-partuclar-resource-cache wiring with a type class (sorry for formatting, I couldn't figure out how to do it properly on blogspot):

    data ResourceCache = ResourceCache
    { _textureCache :: Map String Texture
    , _modelCache :: Map String Model
    }

    makeLenses ''ResourceCache

    class CacheableResource a where
    resourceCache :: Lens' ResourceCache (Map String a)

    instance CacheableResource Texture where
    resourceCache = textureCache

    instance CacheableResource Model where
    resourceCache = modelCache

    That way you can have generic functions that load resources of particular type and store them in cache:

    loadResource :: (MonadState ResourceCache m, CacheableResource r) => String -> (String -> IO r) -> m r
    loadResource resourceName loader = do
    cache <- use resourceCache
    mCachedResource <- Map.lookup name cache
    case mCachedResource of
    Just resource -> return resource
    Nothing -> do
    resource <- liftIO $ loader name
    resourceCache .= Map.insert name resource cache
    return resource

    ReplyDelete
    Replies
    1. That’s interesting, but I keep thinking flexibility is needed. Even though you forbid the user from adding types, when YOU add types, you’ll have a lot of work to do to support new types with such a solution – even though I like it and in the first version of my framework, I used something similar. I didn’t use a Lens' but a HasCache typeclass to implement the getter and setter of your Lens'.

      Delete
  3. Dmitry, speaking of your "Implicit pure store" option -- why wouldn't the following work:

    class Resource rsrc name | rsrc -> name, name -> rsrc where
    loadResource :: (MonadState (Map name rsrc) m,...)
    => name
    -> m rsrc
    newtype TexName = TexName String
    instance Resource Texture Texname where
    ...

    ReplyDelete
  4. 1) You actually can express resource pack as the sequence of maps using type families.
    For that you need type-level list of maps & some "class Default d where new :: d" implemented for each such type-level list to fill them with Map.empty.

    2) Your current solution has a problem with unloading resources. Program instance will end up with all textures/meshes in memory. However, if you add uncaching logic into your generic manager, it will stop be a problem.

    2.5) The caching limit(s?) is another question.

    ReplyDelete
    Replies
    1. Your point 2) is right. Currently I don’t feel the need for unloading resources, but I eventually need it, yes.

      I’m interested in your 1). Do you have some code example? I used type-level maps with DataKinds, PolyKinds and TypeFamilies already with indexed monads (see this https://github.com/phaazon/igl/blob/master/src/Graphics/Rendering/IGL/GL.hs#L51), but I’m very new to that. :)

      Delete
  5. Is it somehow possible to use a fixed font in comments? Not very easy to read code without that.. : -)

    P.S. Dimitri, I'm sorry for misspelling your name above..

    ReplyDelete
  6. For the Digital Software Asset Management this blog is really helpful.
    I appreciate your hard work that makes this blog informative in the Digital Software Asset Management.
    Digital Asset Management Software

    ReplyDelete
  7. Thanks for always being the source that explains things instead of just putting an unjustified answer out there. I loved this post.
    outdoor action camera

    ReplyDelete
  8. This is easier and surely gives comfort to internet users. Thanks for sharing. Post like this offers great benefit. Thank you!
    wifi inspection camera

    ReplyDelete
  9. Thanks for sharing such useful information. Please keep sharing more about Asset Management.

    ReplyDelete
  10. I like your post & I will always be coming frequently to read more of your post. Thank you very much for your post once more.
    guttering cleaning tools

    ReplyDelete
  11. There is a lot of info on this blog: very helpful
    alarm security company

    ReplyDelete
  12. Thanks for sharing the information and this will help full to all.

    Chrysler Replacement Radiators & radiator auto

    ReplyDelete
  13. asset management software in a real time 3D engine in Haskell post nice

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. Its been carrying forward to the vital aspects and ideas which are mostly considered so evident and hopefully by the time we would be able to substantiate every possible stance in this regard. appointment booking software

    ReplyDelete
  16. It looks great blog..Good information shared.It is interesting.
    IMT ref cam

    ReplyDelete
  17. The blog article very surprised to me! Your writing is good. In this I learned a lot! Thank you!
    Electronic locks

    ReplyDelete
  18. Nice blog, good read.

    http://www.qualitecservices.com
    sales@qualitecservices.com

    ReplyDelete
  19. This was certainly a good read. Best Asset Management Software can help you find asset management software that best suits your needs

    ReplyDelete
  20. I’ve read this post and if I could I want to suggest you few interesting things or suggestions.You can write next articles referring to this article. I desire to read even more things about it..
    Asset Management Software
    Asset Tracking Software
    Asset Management Software India
    Asset Management Software Chennai

    ReplyDelete
  21. I think great site for these post and i am read the most of contents have useful for my Carrier.Thanks for these useful information.Any information are commands like to share him.
    Asset Management Software
    Asset Management Software UAE
    Asset Management Software Abu Dhabi
    Asset Tracking Software
    IT Asset Management Software
    Fixed Asset Management Software

    ReplyDelete
  22. Best Corporate Video Production Company in Bangalore and ents Explainer Video Company in Bangalore , 3d, 2d Animation Video Makers in Chennai.
    Nice article. Very much informative. Keep writing and share information

    ReplyDelete
  23. Sarswatienterprises provides high quality Flip off Seals Machinery, Aluminum Foil Converting Machine Suppliers in Delhi and Power Press Manufacturer in Delhi at low cost. putlocker

    ReplyDelete
  24. Aside from managing a company's assets, asset management advisors also provide feedback to their clients, making them aware of their assets. nam group

    ReplyDelete
  25. Law Assignment Help because one cannot know all the information of the world. Now, by the end of the course, one would definitely get to learn the significance of taking help sometimes and managing their time carefully.

    ReplyDelete
  26. Searching for the Geography assignment help online in the USA ? Then you are at the right place. Our team of professionals is highly proficient in providing online help for geography assignments.

    ReplyDelete
  27. Still, searching for the SPSS assignment help? Don’t worry we are here to help you with the SPSS assignment. Our experts are highly proficient in SPSS assignment writing, we provide plagiarism-free, supreme quality assignments.

    ReplyDelete
  28. Thanks for looking forward to more for this wonderful information. I really appreciate your efforts to write such amazing content for us. Are you looking for online essay help at a reasonable price?

    ReplyDelete
  29. ISO 45001 is a globally recognized Occupational Health and Safety Management System (OH&SMS) standard. This international standard provides requirements and as well as specifications to establish, monitor, maintain, implement, and improve the OH&S performance of the organizations. ISO 45001 Certification in Israel

    ReplyDelete
  30. Choose our professional writers and leave all your tensions of researching critical college assignments on our shoulders! GoAssignmentHelp.com.au are equipped with a vast team of professionals and knowledgeable topics tutors and experienced who make sure that you will get the assignment help online you deserve for. We have service team who are available 24 x 7. You can send your questions through email, chat, or send a Whatsapp message. We will provide you quick response to every question about your university assignment help australia related. If you need help with your documents, why not give our professional service a try today? Don’t waste your precious time and contact to our Assignment Provider. GoAssignmentHelp.com.au know that your time value. Call us now and get best Finance, Accounting, Business Law, Computer Science, Statistics, Management, Engineering many topic related assignment service.

    ReplyDelete
  31. This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here keep up the good work 온라인카지노

    ReplyDelete
  32. Thanks for the marvelous posting! I certainly enjoyed reading it, you’re a great author. I will ensure that I bookmark your blog and may come back from now on. I want to encourage you to continue your great writing, have a nice day! 온라인카지노

    ReplyDelete
  33. I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work. 카지노

    ReplyDelete
  34. Great post! For taking the Online Assignment Helper USA you should visit our assignment writing portal. On our portal, we provide all types of assignment writing help which you want to take.

    ReplyDelete
  35. thanks for this really helpful for me as we are in a new generation all things change in a blink of eyes.
    파워볼사이트

    ReplyDelete
  36. Are you struggling to get the online assignment help service in australia? You shouldn’t! Get the best quality assignment help from experts with Ph.D. and master's degrees. Visit our website now to know more about our services.
    Read More:- Assignment Help

    ReplyDelete
  37. You have a real ability for writing unique content. I like how you think and the way you represent your views in this article. I agree with your way of thinking. Thank you for sharing.
    오피월드

    oworldsmewep

    ReplyDelete
  38. You actually make it seem so easy with your presentation but I find this matter to be really something which I think I would never understand. It seems too complex and extremely broad for me. I am looking forward for your next post, I’ll try to get the hang of it!

    성인야설

    ReplyDelete
  39. Thanks for ones marvelous posting! I truly enjoyed reading it, you will be a great author. I will make sure to bookmark your blog and will often come back sometime soon. I want to encourage yourself to continue your great writing, have a nice holiday weekend!

    대딸방

    ReplyDelete
  40. Hi, I do think this is an excellent web site. I stumbled upon it �� I’m going to return once again since I saved as a favorite it. Money and freedom is the best way to change, may you be rich and continue to guide other people.

    외국인출장

    ReplyDelete
  41. Remarkable! Its really amazing post, I have got much clear idea regarding from
    this piece of writing. 파워볼 하는법

    ReplyDelete
  42. I find reading this article a joy. It is extremely helpful and interesting and very much looking forward to reading more of your work 토토

    ReplyDelete
  43. I’m not that much of a internet reader to be honest but your blogs really nice, keep it. 바카라사이트

    ReplyDelete
  44. Nice response in return of this question with real arguments and explaining the whole thing about that.온라인카지노

    ReplyDelete
  45. Quickbooks also offers email support which can be accessed through both their website and through dialling Quickbooks Phone Number +1 855-756-1077. The number for live help is actually only available if you are using the United States version of QuickBooks, but it’s free to call anyway.

    ReplyDelete
  46. So it is interesting and very good written and see what they think about other people
    청마담

    magosucowep

    ReplyDelete
  47. scorpio rising appearance has intense eyes. They're crystal clear and genuinely intimidating. You can't escape the scrutinizing look in the eyes of others.

    ReplyDelete
  48. Opt for our Assignment help online to finish your assignments and submit them within the deadline. No need to take the stress of insufficient knowledge and lack of skills when you have an online assignment writing expert for writing your assignment in Ireland.

    ReplyDelete
  49. Looking for a Geography Assignment Help in the United States? So, all you have to do is visit our website and obtain the greatest helper for your geography assignment at very low charges.

    ReplyDelete
  50. Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too. There tend to be not many people who can certainly write not so simple posts that artistically. Continue the nice writing 먹튀검증

    ReplyDelete
  51. I love the way you write and share your niche! Very interesting and different! Keep it coming!

    ReplyDelete
  52. I admire your contents of weblog shared. Your sense of humor in blog is highly value and appreciated. This info has being one of my best interested one today. Visit here khadija university cut off mark for law

    ReplyDelete
  53. Experts in Managerial Economics Assignment Help will supply students with numerical results to their questions about their assignments. Students will consult with graduate and postgraduate experts in the subject of managerial economics. Students in economics may now take advantage of the world-class assignment writing services that are now available to them.

    ReplyDelete
  54. https://gamebegin.xyz It is possible to exercise alone. A pitching equipment permits you to establish the pace of your soccer ball. By packing a number of baseballs into the device, you are able to practice striking without the need for a pitcher. This electronic equipment is perfect for those who wish to practice baseball alone. Pitching models can be acquired on your community sporting merchandise retailer.

    ReplyDelete
  55. https://gameboot.xyz You see them on periodicals and so on TV, people who seem like their biceps and triceps and thighs and legs will explode since their muscle groups are so large! There is not any need so that you can get the body to this level in the event you don't want to, because the basic strategies on this page will assist you to create muscle in the healthier way.

    ReplyDelete
  56. You were great and everyone received so much from your experience and knowledge. Absolutely amazing, thank you for sharing your knowledge with me. 슬롯머신사이트

    ReplyDelete
  57. virgo rising appearance A Virgo ascendant woman usually has a beautiful delicate frame and striking facial features. These women have a pointy nose and fuller lips.

    ReplyDelete
  58. Wonderfull content,Nice Blog. if you are looking for Quickbooks Customer Service you can contact us at.+1 855-444-2233,Hawaii.

    ReplyDelete
  59. Great blog. Vast knowledge of complete the day through yoga yoga , International Day you reach us at

    ReplyDelete
  60. Telangana is rich in natural wonders and tourism attractions. Whether you're seeking for natural beauty, architecture, or historical information, we've produced a list of Tourist places in Telangana that will leave you breathless in their sheer majesty. The state, which was once part of Andhra Pradesh, is rich in historical sites and religious sanctuaries. Telangana, on the other hand, became India's 29th state on June 2, 2014. Look into historic architecture if you're interested in history and holy sites. Three of Telangana's most prominent tourist destinations are Hyderabad, Medak, and Adilabad. Nizamabad is a well-known tourist destination due to its unique blend of culture, history, and architecture.
    Tourist places in Telangana

    ReplyDelete
  61. Thanks so much for bringing this awesome information to our notice. I had a lot going on my mind now after surfing through this post. I appreciate you for sharing. Also visit fulafia approved school fees schedule for freshers

    ReplyDelete
  62. its really approaching and appealing content for reading and implementation purpose.
    property management software uae

    ReplyDelete
  63. Fantastic review! In my view, if all web owners and bloggers made good content material as you did, the internet shall be much more helpful. I enjoyed gaining ideas from what you've shared. Thanks very much for sharing. kwasu pre-degree remedial admission form

    ReplyDelete
  64. very informative and impressive article.Thanks for sharing with us
    What Should I Wear

    ReplyDelete
  65. Great post! I must thank you for this informative read.
    HRMS Software Dubai

    ReplyDelete
  66. http://phaazon.blogspot.com/2015/06/asset-management-in-real-time-3d-engine.html

    ReplyDelete