Proper implementation of the treadmill algorithm

[caizixian]

The current TreadMill is a misnomer, as it uses HashSets rather than linked lists. It was used during our prototyping phase as a "drop-in" replacement of a real treadmill.

So,

1. We should implement the actual treadmill algorithm with linked lists
2. Evaluate the best approach as to scalability of large object allocation. @wenyuzhao has found that our page allocator doesn't scale well with the increasing parallelism on modern CPUs. For certain workload, the scalability of large object allocation might matter, and a simple lock protecting the whole treadmill might not be the best solution

cc @steveblackburn

[qinsoon]

1. We should implement the actual treadmill algorithm with linked lists

What do you mean by 'the actual treadmill algorithm'? Are you referring the treadmill in Java MMTk/JikesRVM, or the Baker's treadmill in his paper?

To my understanding, treadmill in MMTk core approximately equals treadmill in JikesRVM, and they both are different from the Baker's treadmill. They both use multiple lists/sets to mimic a 'logical' treadmill rather than using an actual cyclic doubly linked list (Baker's). They both allow objects of different sizes in the same treadmill, and allocation is done by actually allocating memory rather than reusing free nodes in the treadmill (Baker's). The differences between MMTk core and JikesRVM are: 1. JikesRVM uses doubly linked list, and mmtk-core uses hashset, and 2. JikesRVM stores links along with payload, and mmtk-core only puts object references in the set (payload is separated from the metadata).

2. Evaluate the best approach as to scalability of large object allocation. @wenyuzhao has found that our page allocator doesn't scale well with the increasing parallelism on modern CPUs. For certain workload, the scalability of large object allocation might matter, and a simple lock protecting the whole treadmill might not be the best solution

The page allocator is in the page resource implementation, rather than the treadmill. If we have scalability issue with page allocator, fixing treadmill won't directly help.