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

[MutantJohn]

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.

[Elysia]

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

[manasij7479]

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.]

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.

[Hodor]

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

[rcgldr]

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.

[Mario F.]

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]

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

[cyberfish]

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.

[cyberfish]

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.

[MutantJohn]

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.

[Elysia]

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.

[Yarin]

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

There's an old saying:

There are only two hard things in Computer Science: Cache invalidation, and naming things.

[Yarin]

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]

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...