[prev in list] [next in list] [prev in thread] [next in thread] 

List:       python-dev
Subject:    [Python-Dev] Re: Compacting the Uncompactable
From:       Tim Peters <tim.peters () gmail ! com>
Date:       2019-09-28 22:18:57
Message-ID: CAExdVN=SpikaMbX9QZVDc4HDfNMPYe4=cRcomCDmrcOW7thcyw () mail ! gmail ! com
[Download RAW message or body]

Short course:  a replacement for malloc for use in contexts that can't
"move memory" after an address is passed out, but want/need the
benefits of compactification anyway.

Key idea:  if the allocator dedicates each OS page to requests of a
specific class, then consider two pages devoted to the same class,
where `-` is free space, and X and Y are allocated chunks:

page1: X--XX-X---X
page2: --Y--Y--YY-

Because there's no overlap in the offsets of allocated blocks here, we
can copy the 4 Ys into page1 (or Xs into page2).  Then tell the OS to
change its page tables so that the virtual addresses of page1 amd
page2 _both_ map to the physical page page1 referred to.  page2's
physical page can be returned to the OS then.

No _virtual_ address malloc ever handed out needs to change.

The rest is making this all safe & "go fast".

On Sat, Sep 28, 2019 at 2:06 PM MRAB <python@mrabarnett.plus.com> wrote:
> 
> Here's a video about memory fragmentation and compaction that you might
> find interesting:
> 
> "Compacting the Uncompactable" by Bobby Powers
> https://www.youtube.com/watch?v=c1UBJbfR-H0
> _______________________________________________
> Python-Dev mailing list -- python-dev@python.org
> To unsubscribe send an email to python-dev-leave@python.org
> https://mail.python.org/mailman3/lists/python-dev.python.org/
> Message archived at \
> https://mail.python.org/archives/list/python-dev@python.org/message/G6OR45TETKIFZDVWAK5ZGLLFTIC422TG/
> 
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/VMP5RXVQV574SXNJC5SNIJNAL3PYZZC6/



[prev in list] [next in list] [prev in thread] [next in thread]