| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Let RingBuf have a logical name for a concrete type, and Deque is
used for the Deque trait (implemented by RingBuf and dlist).
|
|
The free-standing functions in f32, f64, i8, i16, i32, i64, u8, u16,
u32, u64, float, int, and uint are replaced with generic functions in
num instead.
If you were previously using any of those functions, just replace them
with the corresponding function with the same name in num.
Note: If you were using a function that corresponds to an operator, use
the operator instead.
|
|
|
|
|
|
We need a reasonably small initial capacity to make Deques faster
for the common case.
|
|
The deque is split at the marker lo, or logical index 0. Move the
shortest part (split by lo) when growing. This way add_front is just as
fast as add_back, on average.
|
|
The previous implementation of reverse iterators used modulus (%) of
negative indices, which did work but was fragile due to dependency on
the divisor.
|
|
|
|
The deque is determined by vec self.elts.len(), self.nelts, and self.lo,
and self.hi is calculated from these.
self.hi is just the raw index of element number `self.nelts`
|
|
So that deque can be used with IteratorUtil::collect()
|
|
Fix some issues with the deque being very slow, keep the same vec around
instead of constructing a new. Move as few elements as possible, so the
self.lo point is not moved after grow.
[o o o o o|o o o]
hi...^ ^.... lo
grows to
[. . . . .|o o o o o o o o|. . .]
^.. lo ^.. hi
If the deque is append-only, it will result in moving no elements on
grow. If the deque is prepend-only, all will be moved each time.
The bench tests added show big improvements:
Timed using `rust build -O --test extra.rs && ./extra --bench deque`
Old version:
test deque::tests::bench_add_back ... bench: 4976 ns/iter (+/- 9)
test deque::tests::bench_add_front ... bench: 4108 ns/iter (+/- 18)
test deque::tests::bench_grow ... bench: 416964 ns/iter (+/- 4197)
test deque::tests::bench_new ... bench: 408 ns/iter (+/- 12)
With this commit:
test deque::tests::bench_add_back ... bench: 12 ns/iter (+/- 0)
test deque::tests::bench_add_front ... bench: 16 ns/iter (+/- 0)
test deque::tests::bench_grow ... bench: 1515 ns/iter (+/- 30)
test deque::tests::bench_new ... bench: 419 ns/iter (+/- 3)
|
|
Add a test that excercises deque growing.
Add bench tests for grow, new, add_back, add_front, to expose how slow
these functions are.
|
|
Without this, it will hit the assert in fn grow after 32 consecutive
add_front.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
replaced with mutable implementations of Iterator
|
|
|
|
|
|
|
|
As called for in #4994
|
|
to libextra
|
|
This only changes the directory names; it does not change the "real"
metadata names.
|
