u/QuietReader42
Can on demand paging be used to implement dynamic arrays?
Dynamic arrays, for instance std::vector in c++ are implemented based on the idea that if their size exceeds their capacity, the underlying array is reallocated to one that is twice the current capacity. My question is, would this even be necessary given that at least in Linux, pages are allocated to a process on demand? For instance, with a simple program like this: #include <stdio.h> #include <stdlib.h> int main() { long size = (long)(64 * 4096 * 64) * 8; long *arr = malloc(size); for(long i=0; i < (size/32); i++) { arr[i] = i; printf("%d\n", arr[i]); } printf("--->%p\n", arr); while(1) ; } if size were equal to 64 * 4096 * 64, we can see via /proc/[PID]/maps that the heap section is about 4M(despite the malloc being for 16M) and with the size given in the program it is about 32M(despite the malloc being for 128M), illustrating on demand paging. Considering that this implementation is probably not used widely, why is that? I figured one explanation would be the assumption of the system having on demand paging at all, which simply might not be the case, thus reducing portability, but what am I missing otherwise?
I'm feeling betrayed!!!! ;_;
So I have some time off and I'm relearning Haskell, and part of the charm was coming back to cute recursive, lazy, infinite definitions like this: fibSequence :: [Integer] fibSequence = 0 : 1 : zipWith (+) fibSequence (tail fibSequence) which is a pretty good way to define the Fibonacci sequence. And then I was looking around and watching this video, which is really fun, which gives primeSequence :: [Integer] primeSequence = sieveOfEratosthenes [2..] sieveOfEratosthenes :: [Integer] -> [Integer] sieveOfEratosthenes (p:ps) = p : sieveOfEratosthenes [ x | x <- ps, x `mod` p /= 0] And I was like OMG GENIUS! Nice. And then later I tried using this to solve problems in Project Euler, and realized quickly that this indeed is NOT the proper sieve of Erastosthenes, because it does multiple cancellations for each number. So I had to go down a rabbit hole, which has shown me that truly lazy infinite structures are VERY HARD TO WRITE.
Hi everyone
Hi everyone, I’m QuietReader42. I mostly read more than I post, but I’ve been programming in C for a while and I’m interested in systems programming, compilers, memory layout, and Unix-style tools. Lately I’ve also been looking at OCaml because I like the idea of using functional programming for compilers and interpreters. I’m here to follow good technical discussions and occasionally ask questions when I get stuck.