Shrink Span

[emberian]

Span is how we know what source a given piece of the AST corresponds to. There are many, many Spans when compiling a crate. It is currently 16 bytes.

Since a span is always contiguous, it can be compressed by storing the base (u32) plus a length (u16). Furthermore, expn_info is currently occupying a full 8 bytes. It could be replaced with a u16 index into some expn_info table somewhere.

[emberian]

Though, I'm not sure if there are few enough ExpnInfos for this to work.

Maybe we could have a "phantom span". When the high bit of the base is set, use the rest of it as the index into a table that contains the real span and the expninfo.

[emberian]

And long term I think we should just have a NodeId -> Span map instead of storing spans where we think they might be important.

[emberian]

@huonw raises the point of module spans for files over 64K.

[emberian]

Could extend the idea of phantom span and and use another bit to mean "hugespan", which it then looks up in yet another table.

[emberian]

But that brings us down from 4G to 1G of max source code size, which isn't very nice.

[emberian]

Actually I'm not sure that's a problem, given that it can use the rest of the base as an index in the hugespan table.

[emberian]

I think my original idea is flawed but I believe we can do better in 64 bits than what we do today.

[huonw]

I wonder if we could do something like

struct Span {
    start: u32,
    is_huge: u1,
    len_or_hugelen_index: u7,
    expn_info_index: u24
}

(stored as (u32, u32) presumably)

i.e. assume that most spans are less than 128 bytes long, and, if it's longer, index into a table using a combination of start and len_or_hugelen_index (this requires that we can have at most 128 long spans starting at any given byte, which seems reasonable).

It might be worth making a compiler with no spans (or making them zerosized), to estimate the absolute largest gain we can get from changing them, since it may turn out that Spans are lost in the noise of being stored in the larger AST structures.

[emberian]

That is along the lines of what I was thinking as well.

[emberian]

@eddyb do you want to do this?

[eddyb]

I wish I had the time to fiddle with it, sorry.
I should point out that CodeMap is already required for making sense of a Span, so all extra tables can be placed there.

[ghost]

I'm happy to take a look.

[huonw]

Ok, I investigated the absolute maximum gain we can get from working on this, by replacing all the spans in the AST with (), and removing (essentially) all mentions of Span from librustc. Doing this blunt change breaks various things, in particular, macros can no longer be exported, so the bootstrap can't even get past stage1 libcore.

However, I could still compare on the following no_std file, which abuses macros and exponential growth to generate a pile of nested modules/functions/expressions:

#![no_std]
#![feature(lang_items, macro_rules)]

// Pull in the system libc library for what crt0.o likely requires
extern crate libc;

pub enum Option<T> { None, Some(T) }

#[inline(never)]
fn f(x: uint) -> uint { x + 1 }
macro_rules! create_exprs {
    ($e: expr; ) => { ::f(::f($e) + ::f($e)) };
    ($e: expr; $_x: expr $($xs: expr)*) => {
        {
            let a = create_exprs!($e; $($xs)*);
            let b = create_exprs!($e; $($xs)*);
            let c = create_exprs!($e; $($xs)*);
            let d = create_exprs!($e; $($xs)*);
            let e = create_exprs!($e; $($xs)*);
            let f = create_exprs!($e; $($xs)*);
            let g = create_exprs!($e; $($xs)*);
            let h = create_exprs!($e; $($xs)*);
            if a + b == 0 {
                c + d
            } else if e + f == 0 {
                g
            } else {
                h
            }
        }
    }
}

macro_rules! create {
    ($i: item; ) => { $i };
    ($i: item; $_x: expr $($xs: expr)*) => {
        mod foo { create!($i; $($xs)*) }
        mod bar { create!($i; $($xs)*) }

        pub fn baz(x: ::Option<uint>) -> ::Option<uint> {
            use None;
            let z = match x {
                ::Some(y) if y > 10 => create_exprs!(y; 2 16 128),
                ::Some(z) => create_exprs!(z; 2 16 128),
                None => create_exprs!(0u; 2 16 128)
            };
            bar::baz(bar::baz(foo::baz(foo::baz(::Some(z)))))
        }
    }
}

create!(pub fn baz(x: ::Option<uint>) -> ::Option<uint> {
    #![inline(never)]
    use None;
    match x { ::Some(a) => ::Some(a + 1), None => None }
}; 1 2 4 8 16 32)

// Entry point for this program
#[start]
fn start(_argc: int, _argv: *const *const u8) -> int {
    match bar::baz(foo::baz(foo::baz(None))) {
        Some(x) => x as int,
        None => 0
    }
}

// These functions are invoked by the compiler, but not
// for a bare-bones hello world. These are normally
// provided by libstd.
#[lang = "stack_exhausted"] extern fn stack_exhausted() {}
#[lang = "eh_personality"] extern fn eh_personality() {}

Anyway, I measured the memory use with /usr/bin/time, giving 1103420KB for the baseline compiler (nightly 46a3314 2014-07-17 20:07:43 +1000), vs. 973376KB for the one with zero-sized spans, so, about 12% memory saving. (Keep in mind this is making every span 0 sized, so the real gains may be much smaller than this.)

@cmr: would it be feasible to run a mem bench of my code on the file above?

[emberian]

@huonw yes, I can do that later.

On Fri, Jul 18, 2014 at 6:48 AM, Huon Wilson notifications@github.com
wrote:

Ok, I investigated the absolute maximum gain we can get from working on
this, by replacing all the spans in the AST with (), and removing
(essentially) all mentions of Span from librustc. Doing this blunt change
breaks various things, in particular, macros can no longer be exported, so
the bootstrap can't get past stage1 libcore.

However, I could still compare on the following no_std file, which abuses
macros and exponential growth to generate a pile of nested
modules/functions/expressions:

#![no_std]#![feature(lang_items, macro_rules)]
// Pull in the system libc library for what crt0.o likely requiresextern crate libc;
pub enum Option { None, Some(T) }
#[inline(never)]fn f(x: uint) -> uint { x + 1 }macro_rules! create_exprs {
($e: expr; ) => { ::f(::f($e) + ::f($e)) };
($e: expr; $x: expr $($xs: expr)) => {
{
let a = create_exprs!($e; $($xs));
let b = create_exprs!($e; $($xs));
let c = create_exprs!($e; $($xs));
let d = create_exprs!($e; $($xs));
let e = create_exprs!($e; $($xs));
let f = create_exprs!($e; $($xs));
let g = create_exprs!($e; $($xs));
let h = create_exprs!($e; $($xs));
if a + b == 0 {
c + d
} else if e + f == 0 {
g
} else {
h
}
}
}}
macro_rules! create {
($i: item; ) => { $i };
($i: item; $x: expr $($xs: expr)) => {
mod foo { create!($i; $($xs)) }
mod bar { create!($i; $($xs)) }

    pub fn baz(x: ::Option<uint>) -> ::Option<uint> {
        use None;
        let z = match x {
            ::Some(y) if y > 10 => create_exprs!(y; 2 16 128),
            ::Some(z) => create_exprs!(z; 2 16 128),
            None => create_exprs!(0u; 2 16 128)
        };
        bar::baz(bar::baz(foo::baz(foo::baz(::Some(z)))))
    }
}}

create!(pub fn baz(x: ::Option) -> ::Option {
#![inline(never)]
use None;
match x { ::Some(a) => ::Some(a + 1), None => None }}; 1 2 4 8 16 32)
// Entry point for this program#[start]fn start(_argc: int, _argv: *const *const u8) -> int {
match bar::baz(foo::baz(foo::baz(None))) {
Some(x) => x as int,
None => 0
}}
// These functions are invoked by the compiler, but not// for a bare-bones hello world. These are normally// provided by libstd.#[lang = "stack_exhausted"] extern fn stack_exhausted() {}#[lang = "eh_personality"] extern fn eh_personality() {}

Anyway, I measured the memory use with /usr/bin/time, giving 1103420KB
for the baseline compiler (nightly 46a3314
46a3314 2014-07-17 20:07:43
+1000), vs. 973376KB for the one with zero-sized spans, so, about 12%
memory saving. (Keep in mind this is making every span 0 sized, so the real
gains may be much smaller than this.)

@cmr https://github.com/cmr: would it be feasible to run a mem bench of my
code https://github.com/huonw/rust/tree/span-%28%29 on the file above?

—
Reply to this email directly or view it on GitHub
#15594 (comment).

http://octayn.net/

[emberian]

@huonw Can't build the example with stage1 rustc:

Stdout:  | task 'rustc' failed at 'encoding a macro', /home/cmr/src/rust/src/librustc/metadata/encoder.rs:1600
         | 
         | 
Stderr:  | error: internal compiler error: unexpected failure
         | note: the compiler hit an unexpected failure path. this is a bug.
         | note: we would appreciate a bug report: http://doc.rust-lang.org/complement-bugreport.html
         | note: run with `RUST_BACKTRACE=1` for a backtrace

[huonw]

@cmr hm, it works for me. The bootstrap fails building stage1 libcore, but I can still use the first bootstrapped compiler to build the example I gave above (since it's no_std and even avoids core):

$ LD_LIBRARY_PATH=~/rust/build/x86_64-unknown-linux-gnu/stage1/lib/ ~/rust/build/x86_64-unknown-linux-gnu/stage1/bin/rustc nostd.rs -Z time-passes
time: 0.001 s   parsing
time: 0.000 s   gated feature checking
time: 0.000 s   crate injection
time: 0.000 s   configuration 1
time: 0.000 s   plugin loading
time: 0.000 s   plugin registration
time: 6.028 s   expansion
time: 0.688 s   configuration 2
time: 0.732 s   maybe building test harness
time: 0.000 s   prelude injection
time: 0.983 s   assigning node ids and indexing ast
time: 0.079 s   checking that all macro invocations are gone
time: 0.084 s   external crate/lib resolution
time: 0.145 s   language item collection
time: 1.835 s   resolution
time: 0.077 s   lifetime resolution
time: 0.076 s   looking for entry point
time: 0.076 s   looking for plugin registrar
time: 0.215 s   freevar finding
time: 0.466 s   region resolution
time: 0.084 s   loop checking
time: 0.126 s   stability index
time: 0.084 s   type collecting
time: 0.195 s   variance inference
time: 0.184 s   coherence checking
time: 4.880 s   type checking
time: 0.091 s   check static items
time: 0.473 s   const marking
time: 0.074 s   const checking
time: 0.975 s   privacy checking
time: 0.206 s   intrinsic checking
time: 0.252 s   effect checking
time: 0.282 s   match checking
time: 10.996 s  liveness checking
time: 6.158 s   borrow checking
time: 0.519 s   kind checking
time: 0.000 s   reachability checking
time: 0.549 s   death checking
time: 1.482 s   lint checking
time: 0.000 s   resolving dependency formats
time: 4.426 s   translation
  time: 0.380 s llvm function passes
  time: 0.295 s llvm module passes
  time: 8.808 s codegen passes
time: 9.884 s   LLVM passes
  time: 0.152 s running linker
time: 0.169 s   linking

[michaelwoerister]

I've tried to measure span memory consumption by doubling span size instead of setting it to zero (https://github.com/michaelwoerister/rust/tree/span-memory-bench). This way things don't break and one can test against existing codebases. Here are some numbers:

                 SINGLE   DOUBLE    DIFF    SPANS (% of total max memory)
LIBSYNTAX        696764   721728   24964     3.6%
LIBRUSTC        1154900  1394124  239224    20.7%
LIBRUSTC_TRANS   518424   547904   29480     5.7%
LIBRUSTC_TYPECK  446160   482856   36696     8.2%
LIBSTD           243796   260420   16624     6.8%

Numbers are max resident set in KB.

[llogiq]

This works out to:

            SINGLE   DOUBLE   DIFF   SPANS (% of total max memory)
    TOTAL   3060044 3407032 346988  11,34%

[brson]

Is this still relevant? Is anybody still interested in reducing that 11% of space occupied by spans? Would reducing this number really impact compiletime meaningfully?

[michaelwoerister]

I'll just link this here for documentation: https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/23 -- One possible strategy for reducing span sizes.