erg-lang / erg

A statically typed language compatible with Python
http://erg-lang.org
Apache License 2.0
2.65k stars 55 forks source link

TokenStream use VecDeque instead of Vec #292

Closed GreasySlug closed 1 year ago

GreasySlug commented 1 year ago

Currently the tokenStream uses Vec This method has self.lpop() and self.skip

    #[inline]
    fn skip(&mut self) {
        self.tokens.remove(0);
    }

    #[inline]
    fn lpop(&mut self) -> Token {
        self.tokens.remove(0)
    }

This self.remove(0) calculation cost is O(n) For short scripts, the computational cost is not a problem, but for scripts with more than 5k lines, the Parser starts to take a long time to process.

mtshiba commented 1 year ago

It would be more efficient to replace structures other than TokenStream that use Vec internally to perform remove(0) with VecDeque.