Skip to content

Compacting the heap without the page table#9704

Closed
xavierleroy wants to merge 1 commit intoocaml:trunkfrom
xavierleroy:compact-no-page-table
Closed

Compacting the heap without the page table#9704
xavierleroy wants to merge 1 commit intoocaml:trunkfrom
xavierleroy:compact-no-page-table

Conversation

@xavierleroy
Copy link
Copy Markdown
Contributor

@xavierleroy xavierleroy commented Jun 23, 2020

This PR removes the last use of the page table in the non-debug runtime system in no-naked-pointers mode.

To provide an alternate implementation of the Is_in_heap predicate, we build an array of major heap chunks, sorted by increasing address, and do binary search in this array.

Performance is very close to the current implementation that uses page table lookups instead. On the synthetic benchmark below, we get:

List length # heap chunks time w/ page table time w/ binary search
10_000_000 42 0.43s 0.45s
50_000_000 53 1.76s 1.78s
100_000_000 58 3.57s 3.69s
200_000_000 63 7.47s 7.52s
400_000_000 68 15.14s 15.27s

There might be other implementations of the compactor that make no Is_in_heap tests, so this may not be the best solution. I'm submitting this as a draft pull request to show that we can get rid of the page table entirely and now.

@xavierleroy
compact.c: use private data structure instead of the page table
df8b804 
This removes the last use of the page table in the non-debug runtime
system in no-naked-pointers mode.

The data structure is just an array of major heap chunks, sorted
by increasing address, in which we do binary search.
@xavierleroy
Copy link
Copy Markdown
Contributor Author

xavierleroy commented Jun 23, 2020

The synthetic benchmark. It builds a heap where half the blocks are dead, then compacts.

open Printf

let test n =
  let rec mklist accu1 accu2 n =
    if n <= 0
    then accu1  (* throw away the second list *)
    else mklist (n :: accu1) (n :: accu2) (n - 1) in
  let l = mklist [] [] n in
  printf "Number of heap chunks: %d\n" Gc.((quick_stat()).heap_chunks);
  let start = Sys.time() in
  Gc.compact();
  let stop = Sys.time() in
  printf "Compaction time: %.2f\n" (stop -. start);
  l

let _ =
  let sz = int_of_string Sys.argv.(1) in
  printf "Check: %d\n" (List.length (test sz))

@xavierleroy xavierleroy mentioned this pull request Jun 23, 2020
Merged
@damiendoligez damiendoligez mentioned this pull request Jun 30, 2020
Merged
@xavierleroy
Copy link
Copy Markdown
Contributor Author

xavierleroy commented Jul 13, 2020

Superceded by #9728. Closing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

multicore-prerequisite no-change-entry-needed

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@xavierleroy