[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[csmith-project/csmith] 9ceebb: Optimize with replacing variable vectors with vari...



  Branch: refs/heads/jxyang.variableSet
  Home:   https://github.com/csmith-project/csmith
  Commit: 9ceebb96813edbcbfbe93bf1202314fba7f79e54
      https://github.com/csmith-project/csmith/commit/9ceebb96813edbcbfbe93bf1202314fba7f79e54
  Author: Xuejun Yang <xuejya@microsoft.com>
  Date:   2020-07-05 (Sun, 05 Jul 2020)

  Changed paths:
    M src/ArrayVariable.cpp
    M src/Block.cpp
    M src/Block.h
    M src/Bookkeeper.cpp
    M src/Bookkeeper.h
    M src/CGContext.cpp
    M src/CGContext.h
    M src/Constant.h
    M src/Effect.cpp
    M src/Effect.h
    M src/Expression.h
    M src/ExpressionAssign.h
    M src/ExpressionComma.h
    M src/ExpressionFuncall.cpp
    M src/ExpressionFuncall.h
    M src/ExpressionVariable.cpp
    M src/ExpressionVariable.h
    M src/FactMgr.cpp
    M src/FactMgr.h
    M src/FactPointTo.cpp
    M src/FactPointTo.h
    M src/Function.cpp
    M src/Function.h
    M src/Lhs.cpp
    M src/Lhs.h
    M src/Statement.cpp
    M src/Statement.h
    M src/StatementFor.cpp
    M src/Variable.cpp
    M src/Variable.h
    A src/VariableList.h
    M src/VariableSelector.cpp
    M src/VariableSelector.h

  Log Message:
  -----------
  Optimize with replacing variable vectors with variable sets.

Csmith analyzes and keeps track of list variables throughout the generation. Unfortunately the data
structure chosen, without much thought on the performance impact, was vector. This makes it inefficient
to look up or maintain a non-duplicate list. Many times we insert a variable to the vector after we are
sure the variable is not there. The complexity of insertion is O(n).

This PR switches to unordered set from vectors for maintaining variable lists in class FactPointTo, Block,
and Effect. If the performance improvement is sufficient, the next PR would replace more variable vectors
with variable sets.