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.

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?