Hard Things in Computer Science
blog.frankel.ch
Hard Things in Computer Science
1–10 of 46 posts
Re: Hard Things in Computer Science
#2As another problem of applied CS I also suggest to add "Character Encoding" to the list of strongly underestimated complex problems :)
Re: Hard Things in Computer Science
#3As another problem of applied CS I also suggest to add "Character Encoding" to the list of strongly underestimated complex problems :)
I wholeheartedly agree. I was about to list it as a reference only, then I forgot.
Re: Hard Things in Computer Science
#4TTL certainly isn't the only or even best way to achieve cache invalidation - if the cache stores the result of time-intensive computations, then using a key that is a hash of all the inputs is sufficient (though you still need to deal with cleaning out old entries to reclaim space).
From what I've observed often the "hard" problem with caching is knowing when it makes sense to use it at all - I've seen dramatic improvements in system behavior and reliability both from adding and removing caching.
Re: Hard Things in Computer Science
#5Proving code correct is orders of magnitude harder than the rest IMHO. It is amazing that enough progress has been made that large scale projects like CompCert and seL4 can now be done successfully by small teams of people.
Re: Hard Things in Computer Science
#6As another problem of applied CS I also suggest to add "Character Encoding" to the list of strongly underestimated complex problems :)
Here's a classic article on this topic: https://www.joelonsoftware.com/2003/10/08/the-absolute-minim...
Re: Hard Things in Computer Science
#7I think the hard part of cache invalidation is talking about reliably invalidating caches in response to data changes. If you don't care about stale data then cache invalidation is not at all hard. You can just use TTL. TTL is not hard.
Anyway yeah there are definitely lots of hard things.
Re: Hard Things in Computer Science
#8Not explicitly listed, but obviously hard, by definition, in (theoretical) CS: NP-Hard and NP-Complete problems.
Ex:
* knapsack (fit the most “boxes” into min number of containers, sometimes 4D+ “boxes”)
* traveling salesman
Re: Hard Things in Computer Science
#9TTL certainly isn't the only or even best way to achieve cache invalidation - if the cache stores the result of time-intensive computations, then using a key that is a hash of all the inputs is sufficient (though you still need to deal with cleaning out old entries to reclaim space). From what I've observed often the "hard" problem with caching is knowing when it makes sense to use it at all - I've seen dramatic impr…
Yeah I stopped reading at that point, cache invalidation is not 'also known as TTL'.
Re: Hard Things in Computer Science
#10Proving code correct is orders of magnitude harder than the rest IMHO. It is amazing that enough progress has been made that large scale projects like CompCert and seL4 can now be done successfully by small teams of people.
Interesting... I didn't realize there were large open projects that were formally verified. Are there other examples besides CompCert and seL4?