Like Tree15Likes

How would I go about trying to write my own cache manager?

This is a discussion on How would I go about trying to write my own cache manager? within the Tech Board forums, part of the Community Boards category; So, I've been starting to think about projects outside of meshing. It's not like I'll ever be done meshing but ...

  1. #1
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,074

    How would I go about trying to write my own cache manager?

    So, I've been starting to think about projects outside of meshing. It's not like I'll ever be done meshing but I wanna try something radically different. And no, I'm not expecting it to be easy or that I'll even actually finish. But I wanna learn about it and I wanna know what I'd need to learn to actually learn it.

    And meshing made me learn about computers and hardware and memory and I know I still have a long way to go but do you think it would be possible to learn just this one little subset of kernel design?

    I've heard cache management is implementation designed and it seems low level enough that I'd be able to use C for something that truly relies on C. I mean, if Unix was written in C then I mean, C can write kernel-level code, right?

    So, what do I know about cache management?

    It's basically RAM that operates at your CPU's frequency and doesn't need to be bused around the motherboard.

    It's got a finite size and it needs to behave just like memory in the sense that we can both read and write.

    It needs to intelligently prefetch data (does it prefetch instructions as well? Can I store an instruction set in the cache?) and needs to purge data that quickly becomes unused.

    I feel a naive way of doing this is to store the most relatively used data and have thresholds for when something is now a higher priority to keep in the cache than something that is suddenly lower in the pool.

    I feel it would be ideal to keep the cache as clean as possible.

    As for writing, it'd be simple to just let programs write their output to the cache and the write it back to the system RAM in pages once it's consuming either the rest of the cache pool or a significant fraction thereof.

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,604
    Are you talking about CPU cache? Then you should know that you don't have a way of controlling it (except for subtle hints). You can't read or write it.
    The size of cache depends on the level. There are typically three levels, with around 64 KB for level 1, 256 KB for level 2 and 5 MB for level 3. Each level takes longer to read and write from.
    Cache itself doesn't do much because it's a memory. It's the CPU that does the work, and yes, modern cpus will prefetch both data and instructions and place them into cache memory. In today's computers, there are caches for both instructions and data (separate).

    If you want to know more about computer architectures, I would recommend this book:

    Computer Architecture: A quantitative approach, 5th ed.
    by John Hennessy and David Patterson
    Morgan Kaufmann, 2012
    ISBN: 978-0-12-383872-8
    cyberfish likes this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Real Programmers design their own CPUs !
    Why you are so obsessed with the cache is beyond me.
    Let the compiler figure out how to make your code cache friendly, it'll do a much better job than random hacks.
    Mario F. likes this.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    Designing a database.
    Writing a lexical analyzer + parser.
    Developing a compression algorithm.
    Making an FTP client/server.
    Building a file system.

    These are all things much more interesting and that will help you learn a whole lot more about programming. Cache managers... tsk.
    stahta01 likes this.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    Registered User Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    650
    Quote Originally Posted by Mario F. View Post
    Designing a database.
    Writing a lexical analyzer + parser.
    Developing a compression algorithm.
    Making an FTP client/server.
    Building a file system.

    These are all things much more interesting and that will help you learn a whole lot more about programming. Cache managers... tsk.
    You left out Hodorcrypt
    Mario F. likes this.

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,284
    Assuming you have a reasonably current processor, data cache operations can be enable / disabled by using SSE / MMX intrinsic functions. You'd disable the cache for data that you wouldn't want to end up in the cache. I'm not aware of any similar feature to deal with the translation look aside buffer cache, which is used to map virtual addresses into physical addresses. Also the cache implementation (direct, n-way, fully associative, ...) is different between processors.

  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    Quote Originally Posted by Hodor View Post
    You left out Hodorcrypt
    No way! He's too inexperienced. That's an asymmetric two-way unilogical cipher that adopts a residual block termination mode of operation and employs a powerful summation generator. No primality tests are known. It's too hard. And the thing is, decryption will always return "Hodor". Which greatly confuses beginners.
    Hodor and oogabooga like this.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #8
    Registered User Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    650
    Quote Originally Posted by Mario F. View Post
    No way! He's too inexperienced. That's an asymmetric two-way unilogical cipher that adopts a residual block termination mode of operation and employs a powerful summation generator. No primality tests are known. It's too hard. And the thing is, decryption will always return "Hodor". Which greatly confuses beginners.
    I'm lost for words

  9. #9
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    Cache management IS a very interesting problem. But there's not much you can do on the software side.

    A fun project would be to take a FPGA, design a CPU in VHDL/Verilog (hardware description languages) or take an existing "soft core" without cache, and design a caching system for it.

    That has little to do with software, though.

  10. #10
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    In one of computer architecture courses I have taken, we designed cache systems (n-way associative, levels, replacement scheme, etc) and branch predictors, and simulated running a program in software to see the effect of different configurations. That was endless fun.

    That's purely for educational purposes, though, and doesn't really do anything.

  11. #11
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,074
    Quote Originally Posted by Mario F. View Post
    Designing a database.
    Writing a lexical analyzer + parser.
    Developing a compression algorithm.
    Making an FTP client/server.
    Building a file system.

    These are all things much more interesting and that will help you learn a whole lot more about programming. Cache managers... tsk.
    How do any of those sound interesting?

    Databases? Ew...

    Lexical analyzer and parser? Don't even try. Those'll just make the writers try harder! We will never be replaced with automated speech! Or maybe you work for an advertising firm and want to track buzzwords/phrases...

    Okay, the compression algorithm is cool though. I did some light independent reading about that.

    FTP client/server, that doesn't sound like anything a natural scientist would like at all! I mean, I'll use one if I need one but ew to this one as well...

    And building a file system? That might be kind of neat, actually. Like, how Arch actually resolves package dependencies, etc. That would be really neat because I use it on such a day-to-day basis, I can't help but be curious.

    Here's the thing though, lexical analysis is my weakest aspect of programming. I should dabble in it more so when I get asked about it on a programming interview test, I can actually do it. Okay, maybe the FTP thing would also be really fun to write. Could I use C++ for that? Or is C better in the FTP regard?

    But first thing's first, what's a good lexical analysis problem to work on so that I may better my skills?

    Actually, this one programming interview test totally pwned me in the face.

    Take this string, 1234567890 and this target string, 5000.

    Write code that finds (and displays each) the total number of ways our initial 10 digit string can be decomposed and then combined with addition and multiplication operators equal the target string.

    So let's do a smaller example to really illustrate, consider 1234 and 100.

    1 o 2 o 3 o 4, where o is the operator
    12 o 34
    12 o 3 o 4
    1 o 23 o 4
    etc.

    Basically, brute force is okay but I was too weak at parsing my string and writing the generic algorithm.

    What I did accomplish was code that would take the 10 digit number and store it in a 10 element int array. Idk if that was the right thing to do but eh... Also, this test was in pure C. I think I could've just used char pointers and dereferences but I didn't know that at the time of the test lol.

    I wanted to start from the left and work my way to the right, testing 1 against all combos of 234 which is Idk how many lol.

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,604
    Quote Originally Posted by MutantJohn View Post
    Okay, maybe the FTP thing would also be really fun to write. Could I use C++ for that? Or is C better in the FTP regard?
    You should know answers to these kinds of questions.
    Language-wise, C++ is superior to C, so there would be no reason why C++ would be a bad choice in this regard, right?
    That leaves the question of practicality. What tools do we have? Does there exist tools for C and C++? Are some tools (for some language) better than the others (i.e. compilers, debuggers, IDEs, profilers, etc)?
    Then we have experience. What would take less time? What would use less resources?
    And a more important question for you: what would a specific language get you? What would you gain from using C? What would you gain from using C++?

    As far as I know, there is nothing that cannot be done in C++ (and the same for C). But it is often a question of how good the tools are. If the tools are lacking for a language, then you may have to go with another language.
    So... to sum it up. Choose whatever you feel you will learn most with.
    stahta01 likes this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,627
    Quote Originally Posted by MutantJohn View Post
    How would I go about trying to write my own cache manager?
    There's an old saying:
    Quote Originally Posted by Phil Karlton
    There are only two hard things in Computer Science: Cache invalidation, and naming things.
    stahta01 likes this.
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  14. #14
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,627
    Quote Originally Posted by MutantJohn View Post
    Okay, maybe the FTP thing would also be really fun to write. Could I use C++ for that? Or is C better in the FTP regard?
    Eww FTP. If you want to go that route, you should instead write your own protocol and accompanying client/server. It shouldn't be hard to do better than FTP.
    Elysia likes this.
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  15. #15
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,604
    Quote Originally Posted by Yarin View Post
    Eww FTP. If you want to go that route, you should instead write your own protocol and accompanying client/server. It shouldn't be hard to do better than FTP.
    While you're at it, add pipelining and release it as an open protocol along with source!
    We could use some good protocol for transferring data quickly over internet. It's amazing how few protocols actually take latency into account...
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. D-Cache/I Cache Simulator
    By husslela2 in forum C Programming
    Replies: 7
    Last Post: 04-27-2010, 08:41 AM
  2. Difference between ARP Cache and DNS cache?
    By namasteall2000 in forum Networking/Device Communication
    Replies: 9
    Last Post: 06-26-2009, 08:49 AM
  3. SYnchronize read & write of a cache file
    By lei_michelle in forum C Programming
    Replies: 4
    Last Post: 02-26-2008, 04:49 PM
  4. How to write a session manager?
    By Logan in forum C++ Programming
    Replies: 0
    Last Post: 04-25-2006, 06:34 PM
  5. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 01:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21