4K pages probably used to be too large

By: anon2 (anon.delete@this.anon.com), May 3, 2021 12:17 am
Room: Moderated Discussions
Ben LaHaise (bcrl.delete@this.kvack.org) on May 2, 2021 10:45 am wrote:
> Yuhong Bao (yuhongbao_386.delete@this.hotmail.com) on May 1, 2021 1:01 pm wrote:
> > The fun thing is that 4K pages probably used to be too large. On a 80386, just 8 tasks would consume
> > at least 64k and probably 128k just for the page tables alone. (80386 page tables were two levels)
> The National Semiconductor 32016 had 512 byte page sizes. The problem is that overhead of small
> page sizes becomes excessive as soon as you have more than a couple of megabytes of memory.
> With 16MB of RAM and 512 byte pages that works out to 65536 pages for which data structures
> to track all the individual pages are needed.

That's what Linux does, but it is not necessarily the best size/speed tradeoff for very small memory systems. Tracking per page data with 4k pages and 64 bytes per page is still 25% the overhead of your "unviable" solution, which doesn't sound great when you put it that way. That being said I don't think it's necessarily bad at all.

> Even at 16 bytes of overhead per page, that's
> 1MB or 1/16th of memory.

?? 16 / 512 = 1/32

> For reference Linux has upwards of 64 byte of overhead per page these
> days.

To be clear, Linux uses about 32 bytes of overhead per page on 32-bit machines, or 1/16th of physical memory if you used 512 byte pages.

> The window for which 512 byte pages were viable was closed back in the 1980s.

I don't see how you proved your point, you threw out a bunch of numbers and then said 512 is not viable without ever really proving the case.

And the ratio is the same. 1/16th remains 1/16th whether you have 16MB of ram or 16TB. Actually the 512 page system might easily use significantly _less_ physical memory in real workloads whether you're using it on a 16MB machine or a 16TB one for exactly the same reason Linus does not like 64K pages.

That 32/64 byte tracking per page sounds horrible until you find that you only need to save just one page every 6% of time time vs 4K pages in reduced internal fragmentation overhead to make up for it. Sure you have some other structures, page tables etc that add to the overheads as well, but you would definitely still see some cases where 512 byte pages used less memory even with Linux.

Caching the files in today's Linux with 512 byte pages takes 1149MB, with 4K pages 1316MB, about 15% more. You need to use 87 bytes per page in overhead before 512 overtakes 4K in memory usage there.

Actually I wouldn't be surprised if 512 pages today were even more viable than they were back then, because TLBs and page walk algorithms have been so vastly improved that they're almost as close to a "solved" problem as any hard problem in CPU architecture, whereas back then they were not, and were a really big problem you could easily see double digit percent TLB miss costs in normal workloads.

It's funny the hand wringing over pages still goes on. People (not saying you, but some in CPU / OS space) are terrifed of the huge numbers they come up with by dividing things -- oh no, servers have a *billion* pages to manage, how will we ever cope?! (Answer: exactly the same way we coped when we had a million pages to deal with, and exactly the same way we cope with the *20 billion* cache lines that have to be managed, or the X million objects of application data the CPU has to deal with. Locality of reference. Works nicely for TLBs just as it does for data.

The real reason 4K is a good number and remains a good number is not because of any absolute numbers (millions of pages!!) but just because fragmentation doesn't blow memory usage out too far for structures you want to allocate as page size, and that has not changed much since 1980. 8K would probably be okay, 2K would probably be okay.

512 is not unviable because it uses more memory (it might use less), it just doesn't use that much less that it makes much sense to be so small. But I don't think that's a new thing -- I would say depending on size/speed tradeoffs, it could easily have been a worse choice back in 1980 when TLBs were either tiny or used a lot of area on chip, and misses took huge expensive interrupts.
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
4K pages probably used to be too largeYuhong Bao2021/05/01 12:01 PM
  HDD seek time isn't freeMark Roulo2021/05/01 01:12 PM
    HDD seek time isn't freeYuhong Bao2021/05/01 01:21 PM
      HDD seek time isn't freeTim Mc2021/05/01 01:42 PM
        HDD seek time isn't freerwessel2021/05/01 01:57 PM
  4K pages probably used to be too largeBen LaHaise2021/05/02 09:45 AM
    VAX was 512 (in 1977) (NT)anonymous22021/05/02 07:36 PM
      FWIW, S/370 offered a choice of 2K and 4K (NT)rwessel2021/05/03 04:09 AM
      DEC's earliest PDP-11 disks were 512 (in 1971)John Yates2021/05/03 12:53 PM
    4K pages probably used to be too largeanon22021/05/03 12:17 AM
      4K pages probably used to be too largeBen LaHaise2021/05/03 04:36 PM
        Morotola 680x0 series page sizesBen LaHaise2021/05/03 04:51 PM
        4K pages probably used to be too largeanon22021/05/03 05:39 PM
          4K pages probably used to be too largeanon22021/05/03 07:51 PM
        4K pages probably used to be too largeYuhong Bao2021/05/03 09:51 PM
      4K pages probably used to be too largewumpus2021/05/05 08:06 AM
        4K pages probably used to be too largeanon22021/05/05 03:04 PM
          4K pages probably used to be too largeChester2021/05/05 05:45 PM
            4K pages probably used to be too largewumpus2021/05/06 08:06 AM
              Phenom TLB bugHeikki Kultala2021/05/06 11:46 AM
                Phenom TLB bugChester2021/05/06 04:29 PM
        4K pages probably used to be too largeEtienne Lorrain2021/05/06 12:08 AM
          4K pages probably used to be too largeJames2021/05/06 01:36 AM
            4K pages probably used to be too largerwessel2021/05/06 08:32 AM
              Reformatting SCSI disk sector sizeDoug S2021/05/06 10:30 AM
        4K pages probably used to be too largeDavid Hess2021/05/11 07:57 AM
  Page size is more complex/nuancedPaul A. Clayton2021/05/08 09:03 AM
Reply to this Topic
Body: No Text
How do you spell tangerine? ūüćä