1
\$\begingroup\$

Here is a lexer for a grammar I'm designing. After benchmarking with 1MB files and having several iterations of the lexer, I found that coping the file being read into a buffer and lexing that buffer is the fastest. However, I can't seem to get under 0.3 seconds, and in order to process a file I need to load it into a memory buffer.

I have also found that around 0.1 seconds is spent just moving the file into a buffer; however, if you lex directly from the file using ifstream it tends to increase the time it takes to lex a file anywhere from 0.2 to 0.5 more seconds.

What are some memory and speed optimizations I can do on this code make it faster, if I can?

lexer.h

#ifndef LEXER_H
#define LEXER_H

#include <string>
#include "./ast/token.h"

class ice_lexer {
public:
    std::string source;
    size_t length;

    size_t ptr;
    size_t line;
    size_t pos;

    ice_lexer(const char* src_name);
    ice_token next(void);
private:
    ice_token symbol(ice_type_enum, const std::string, size_t);
    ice_token identifier(void);
    char advance(size_t);
    char look(size_t);
    void new_line(void);
};

#endif

lexer.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <ctype.h>
#include "../ast/token.h"
#include "./ast/lexer.h"

#define DEBUG 0

ice_lexer::ice_lexer(const char* src_name) {
    std::ifstream in(src_name, std::ios::in | std::ios::binary);
    source = (std::string((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()));

    length = source.length();
    line = 1;
    pos = 0;
    ptr = 0;
}

void ice_lexer::new_line(void) {
    this->line++;
    this->pos = 0;

    #if DEBUG
    std::cout << "New line, currently l:" << this->line << " p:" << this->pos << std::endl;
    #endif
}

char ice_lexer::look(size_t offset) {
    if (this->ptr + offset > this->length) {
        #if DEBUG
        std::cout << "Index indexing " << this->ptr + offset << " out of bounds " << this->length << std::endl;
        #endif

        return '\0';
    }

    #if DEBUG
    std::cout << "Looking at \'" << this->source[this->ptr + offset] << "\'" << std::endl;
    #endif

    return this->source[this->ptr + offset];
}

char ice_lexer::advance(size_t offset) {
    this->ptr += offset;
    this->pos += offset;

    #if DEBUG
    std::cout << "Advancing " << offset << std::endl;
    #endif

    return look(0);
}

ice_token ice_lexer::symbol(ice_type_enum t, const std::string str, size_t offset) {
    ice_token token(this, t);
    token.str = str;
    advance(offset);
    return token;
}

ice_token ice_lexer::identifier(void) {
    std::string str = "";
    char c = look(0);
    size_t length = 0;

    while (isalnum(c) || c == '_') {
        str += c;
        advance(1);
        c = look(0);
        length++;
    }

    ice_token token = symbol(ICE_IDENTIFIER, str, length);

    return token;
}

ice_token ice_lexer::next(void) {
    char c = look(0);
    char ca = look(1);

    switch (c) {
    case '+':
        if (ca == '=')
            return symbol(ICE_ADDEQL, "+=", 2);
        else
            return symbol(ICE_ADD, "+", 1);
    case '-':
        if (ca == '=')
            return symbol(ICE_SUBEQL, "-=", 2);
        else
            return symbol(ICE_SUB, "-", 1);
    case '*':
        if (ca == '=')
            return symbol(ICE_MULEQL, "*=", 2);
        else
            return symbol(ICE_MUL, "*", 1);
    case '/':
        if (ca == '=')
            return symbol(ICE_DIVEQL, "/=", 2);
        else
            return symbol(ICE_DIV, "/", 1);
    case '^':
        if (ca == '=')
            return symbol(ICE_MODEQL, "^=", 2);
        else
            return symbol(ICE_MOD, "^", 1);
    case '=':
        if (ca == '=')
            return symbol(ICE_EQLTO, "==", 2);
        else
            return symbol(ICE_ASSIGN, "=", 1);
    case '!':
        if (ca == '=')
            return symbol(ICE_NOTEQL, "!=", 2);
        else
            return symbol(ICE_URNARYNOT, "!", 1);
    case '<':
        if (ca == '=')
            return symbol(ICE_GRTEQL,  "<=", 2);
        else
            return symbol(ICE_GRT, "<", 1);
    case '>':
        if (ca == '=')
            return symbol(ICE_LESEQL, ">=", 2);
        else
            return symbol(ICE_LES, ">", 1);
    case '(':
        return symbol(ICE_RPARA, "(", 1);
    case ')':
        return symbol(ICE_LPARA, ")", 1);
    case '[':
        return symbol(ICE_LBRAC, "[", 1);
    case ']':
        return symbol(ICE_RBRAC, "]", 1);
    case '{':
        return symbol(ICE_LCURL, "{", 1);
    case '}':
        return symbol(ICE_RCURL, "}", 1);
    case '\0':
        return symbol(ICE_EOF, "\\0", 0);
    default:
        if (isalpha(c) || c == '_') {
            return identifier();
        } else if (isspace(c)) {
            while (isspace(look(0)) && look(0) != '\0') {
                if (c == '\n')
                    new_line();

                advance(1);
            }

            #if DEBUG
            std::cout << "..." << std::endl;
            #endif

            return next();
        }

        return symbol(ICE_NONE, "None", 1);
    }
}

(I haven't posted all the code here because token.h is just some class definitions and enums.)

\$\endgroup\$
4
\$\begingroup\$

From looking at our code, I would assume that maintainability isn't important. If so, please add some comments so you understand the purpose of the members ... in six months.

That said, there are already a few things you can do which I've learned are important for performance:

  • Put the implementation of the constructor, destructor ... of ice_token in the header file. Otherwise, you need link-time optimization to inline this.
  • Don't write: std::string str = ""; as this results in having to read the data in the string to construct it. Just use std::string str{};
  • Rethink the arguments for symbol, you will call this method a lot.

Looking more detailed to the symbol function, one could see this almost always being called with a const char *. As a result, you will need to construct a std::string from this. (Which afterwards gets copied)

I would suggest rewriting it to:

ice_token ice_lexer::symbol(ice_type_enum t, const char *str) {
    ice_token token(this, t);
    token.str = str;
    advance(token.str.length());
    return token;
}

If I can remark on your style, I would wonder why you are reinventing pointers yourself. This leads you to always have to request character 'X' while you actually already know in front that you can loop over the characters in this string via the const char * which you can retrieve via std::string::c_str().

One could hope that this is a styling issue without performance effects, though as std::string has short-string optimization, it can prevent extra if-tests which could allow your compiler to better optimize.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.