#1BRC - Introduction

What is 1BRC and Why the Fuzz?

Let's Challenge Ourselves

What We Will Do and What We Won't

The Baseline

The Original Code

public String run(final String fileName) throws IOException {
    Collector<Measurement, MeasurementAggregator, ResultRow> collector = Collector.of(MeasurementAggregator::new,
            (agg, m) -> {
                agg.min = Math.min(agg.min, m.value);
                agg.max = Math.max(agg.max, m.value);
                agg.sum += m.value;
                agg.count++;
            }, (agg1, agg2) -> {
                var res = new MeasurementAggregator();
                res.min = Math.min(agg1.min, agg2.min);
                res.max = Math.max(agg1.max, agg2.max);
                res.sum = agg1.sum + agg2.sum;
                res.count = agg1.count + agg2.count;

                return res;
            }, agg -> {
                return new ResultRow(agg.min, (Math.round(agg.sum * 10.0) / 10.0) / agg.count, agg.max);
            });

    // Measurement is a record
    var result = Files.lines(Paths.get(fileName)).parallel() // <-- optional
            .map(l -> l.split(";"))
            .map(l -> new Measurement(l))
            .collect(groupingBy(m -> m.station(), collector));

    return new TreeMap<>(result).toString();
}
    

org.rschwietzke.devoxxpl24.BRC01_BaselineST
github.com/rschwietzke/1brc-the-first-80-meters.git

The Second Baseline

Stream Tuning is Too Complicated

/**
 * A more classic version
 */
public String run(final String fileName) throws IOException
{
    final Map<String, Temperatures> cities = new HashMap<>();

    try (var reader = Files.newBufferedReader(Paths.get(fileName)))
    {
        String line;
        while ((line = reader.readLine()) != null)
        {
            // split the line
            final String[] cols = line.split(";");

            // get us the data to store
            final String city = cols[0];
            final double temperature = Double.parseDouble(cols[1]);

            // store and sum up the data
            // Map::merge(key, value, remappingFunction)
            cities.merge(city, new Temperatures(temperature), (t1, t2) -> t1.merge(t2));
        }
    }

    // ok, we got everything, now we need to order it
    return new TreeMap<String, Temperatures>(cities).toString();
}
    

org.rschwietzke.devoxxpl24.BRC03_NoStreamST
github.com/rschwietzke/1brc-the-first-80-meters.git

Split is Slow

Get Rid Off split

public String run(final String fileName) throws IOException
{
    // our cities with temperatures
    final Map<String, Temperatures> cities = new HashMap<>();

    try (var reader = Files.newBufferedReader(Paths.get(fileName)))
    {
        String line;
        while ((line = reader.readLine()) != null)
        {
            // split the line
            final int pos = line.indexOf(';');

            // get us the city
            final String city = line.substring(0, pos);
            final String temperatureAsString = line.substring(pos + 1);

            // parse our temperature
            final double temperature = Double.parseDouble(temperatureAsString);

            // merge the data into the captured data
            cities.merge(city, new Temperatures(temperature), (t1, t2) -> t1.merge(t2));
        }
    }

    // ok, we got everything, now we need to order it and print it
    return new TreeMap<String, Temperatures>(cities).toString();
}
    

org.rschwietzke.devoxxpl24.BRC05_ReplaceSplitST

But doesn't split shortcut?

private String[] split(String regex, int limit, boolean withDelimiters) {
    /* fastpath if the regex is a
     * (1) one-char String and this character is not one of the
     *     RegEx's meta characters ".$|()[{^?*+\\", or
     * (2) two-char String and the first char is the backslash and
     *     the second is not the ascii digit or ascii letter.
     */
    char ch = 0;
    if (((regex.length() == 1 &&
            ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
            (regex.length() == 2 &&
                    regex.charAt(0) == '\\' &&
                    (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
                    ((ch-'a')|('z'-ch)) < 0 &&
                    ((ch-'A')|('Z'-ch)) < 0)) &&
            (ch < Character.MIN_HIGH_SURROGATE ||
                    ch > Character.MAX_LOW_SURROGATE))
    {
        // All the checks above can potentially be constant folded by
        // a JIT/AOT compiler when the regex is a constant string.
        // ...
        // This split now creates objects
        return split(ch, limit, withDelimiters);
    }
    ...
}
    

java.util.String::split

Double Parsing

Make double Parsing Less Generic

The Problem in 224 Lines

static ASCIIToBinaryConverter readJavaFormatString( String in ) throws NumberFormatException {
    boolean isNegative = false;
    boolean signSeen   = false;
    int     decExp;
    char    c;

parseNumber:
    try{
        in = in.trim(); // don't fool around with white space.
                        // throws NullPointerException if null
        int len = in.length();
        if ( len == 0 ) {
            throw new NumberFormatException("empty String");
        }
        int i = 0;
        switch (in.charAt(i)){
        case '-':
            isNegative = true;
            //FALLTHROUGH
        case '+':
            i++;
            signSeen = true;
        }
        c = in.charAt(i);
        if(c == 'N') { // Check for NaN
            if((len-i)==NAN_LENGTH && in.indexOf(NAN_REP,i)==i) {
                return A2BC_NOT_A_NUMBER;
            }
            // something went wrong, throw exception
            break parseNumber;
        } else if(c == 'I') { // Check for Infinity strings
            if((len-i)==INFINITY_LENGTH && in.indexOf(INFINITY_REP,i)==i) {
                return isNegative? A2BC_NEGATIVE_INFINITY : A2BC_POSITIVE_INFINITY;
            }
            // something went wrong, throw exception
            break parseNumber;
        } else if (c == '0')  { // check for hexadecimal floating-point number
            if (len > i+1 ) {
                char ch = in.charAt(i+1);
                if (ch == 'x' || ch == 'X' ) { // possible hex string
                    return parseHexString(in);
                }
            }
        }  // look for and process decimal floating-point string

        char[] digits = new char[ len ];
        boolean decSeen = false;
        int nDigits = 0;
        int decPt = 0;
        int nLeadZero = 0;
        int nTrailZero = 0;

    skipLeadingZerosLoop:
        while (i < len) {
            c = in.charAt(i);
            if (c == '0') {
                nLeadZero++;
            } else if (c == '.') {
                if (decSeen) {
                    // already saw one ., this is the 2nd.
                    throw new NumberFormatException("multiple points");
                }
                decPt = i;
                if (signSeen) {
                    decPt -= 1;
                }
                decSeen = true;
            } else {
                break skipLeadingZerosLoop;
            }
            i++;
        }
    digitLoop:
        while (i < len) {
            c = in.charAt(i);
            if (c >= '1' && c <= '9') {
                digits[nDigits++] = c;
                nTrailZero = 0;
            } else if (c == '0') {
                digits[nDigits++] = c;
                nTrailZero++;
            } else if (c == '.') {
                if (decSeen) {
                    // already saw one ., this is the 2nd.
                    throw new NumberFormatException("multiple points");
                }
                decPt = i;
                if (signSeen) {
                    decPt -= 1;
                }
                decSeen = true;
            } else {
                break digitLoop;
            }
            i++;
        }
        nDigits -=nTrailZero;
        //
        // At this point, we've scanned all the digits and decimal
        // point we're going to see. Trim off leading and trailing
        // zeros, which will just confuse us later, and adjust
        // our initial decimal exponent accordingly.
        // To review:
        // we have seen i total characters.
        // nLeadZero of them were zeros before any other digits.
        // nTrailZero of them were zeros after any other digits.
        // if ( decSeen ), then a . was seen after decPt characters
        // ( including leading zeros which have been discarded )
        // nDigits characters were neither lead nor trailing
        // zeros, nor point
        //
        //
        // special hack: if we saw no non-zero digits, then the
        // answer is zero!
        // Unfortunately, we feel honor-bound to keep parsing!
        //
        boolean isZero = (nDigits == 0);
        if ( isZero &&  nLeadZero == 0 ){
            // we saw NO DIGITS AT ALL,
            // not even a crummy 0!
            // this is not allowed.
            break parseNumber; // go throw exception
        }
        //
        // Our initial exponent is decPt, adjusted by the number of
        // discarded zeros. Or, if there was no decPt,
        // then its just nDigits adjusted by discarded trailing zeros.
        //
        if ( decSeen ){
            decExp = decPt - nLeadZero;
        } else {
            decExp = nDigits + nTrailZero;
        }

        //
        // Look for 'e' or 'E' and an optionally signed integer.
        //
        if ( (i < len) &&  (((c = in.charAt(i) )=='e') || (c == 'E') ) ){
            int expSign = 1;
            int expVal  = 0;
            int reallyBig = Integer.MAX_VALUE / 10;
            boolean expOverflow = false;
            switch( in.charAt(++i) ){
            case '-':
                expSign = -1;
                //FALLTHROUGH
            case '+':
                i++;
            }
            int expAt = i;
        expLoop:
            while ( i < len  ){
                if ( expVal >= reallyBig ){
                    // the next character will cause integer
                    // overflow.
                    expOverflow = true;
                }
                c = in.charAt(i++);
                if(c>='0' && c<='9') {
                    expVal = expVal*10 + ( (int)c - (int)'0' );
                } else {
                    i--;           // back up.
                    break expLoop; // stop parsing exponent.
                }
            }
            int expLimit = BIG_DECIMAL_EXPONENT + nDigits + nTrailZero;
            if (expOverflow || (expVal > expLimit)) {
                // There is still a chance that the exponent will be safe to
                // use: if it would eventually decrease due to a negative
                // decExp, and that number is below the limit.  We check for
                // that here.
                if (!expOverflow && (expSign == 1 && decExp < 0)
                        && (expVal + decExp) < expLimit) {
                    // Cannot overflow: adding a positive and negative number.
                    decExp += expVal;
                } else {
                    //
                    // The intent here is to end up with
                    // infinity or zero, as appropriate.
                    // The reason for yielding such a small decExponent,
                    // rather than something intuitive such as
                    // expSign*Integer.MAX_VALUE, is that this value
                    // is subject to further manipulation in
                    // doubleValue() and floatValue(), and I don't want
                    // it to be able to cause overflow there!
                    // (The only way we can get into trouble here is for
                    // really outrageous nDigits+nTrailZero, such as 2
                    // billion.)
                    //
                    decExp = expSign * expLimit;
                }
            } else {
                // this should not overflow, since we tested
                // for expVal > (MAX+N), where N >= abs(decExp)
                decExp = decExp + expSign*expVal;
            }

            // if we saw something not a digit ( or end of string )
            // after the [Ee][+-], without seeing any digits at all
            // this is certainly an error. If we saw some digits,
            // but then some trailing garbage, that might be ok.
            // so we just fall through in that case.
            // HUMBUG
            if ( i == expAt ) {
                break parseNumber; // certainly bad
            }
        }
        //
        // We parsed everything we could.
        // If there are leftovers, then this is not good input!
        //
        if ( i < len &&
            ((i != len - 1) ||
            (in.charAt(i) != 'f' &&
             in.charAt(i) != 'F' &&
             in.charAt(i) != 'd' &&
             in.charAt(i) != 'D'))) {
            break parseNumber; // go throw exception
        }
        if(isZero) {
            return isNegative ? A2BC_NEGATIVE_ZERO : A2BC_POSITIVE_ZERO;
        }
        return new ASCIIToBinaryBuffer(isNegative, decExp, digits, nDigits);
    } catch ( StringIndexOutOfBoundsException e ){ }
    throw new NumberFormatException("For input string: \"" + in + "\"");
}

    

jdk.internal.math.FloatingDecimal::readJavaFormatString/p>

public static double parseDouble(final String s) {
    return parseDouble(s, 0, s.length() - 1);
}

private static final double[] multipliers = {
    1, 1, 0.1, 0.01, 0.001, 0.000_1, 0.000_01, 0.000_001, 0.000_000_1, 0.000_000_01,
    0.000_000_001, 0.000_000_000_1, 0.000_000_000_01, 0.000_000_000_001, 0.000_000_000_000_1,
    0.000_000_000_000_01, 0.000_000_000_000_001, 0.000_000_000_000_000_1, 0.000_000_000_000_000_01};

public static double parseDouble(final String s, final int offset, final int end) {
    final int negative = s.charAt(offset) == '-' ? offset + 1 : offset;

    long value = 0;
    int decimalPos = end;

    for (int i = negative; i <= end; i++) {
        final int d = s.charAt(i);
        if (d == '.') {
            decimalPos = i;
            continue;
        }
        final int v = d - DIGITOFFSET;
        value = ((value << 3) + (value << 1));
        value += v;
    }

    // adjust the decimal places
    value = negative != offset ? -value : value;
    return value * multipliers[end - decimalPos + 1];
}
    

org.rschwietzke.devoxxpl24.BRC06_NewDoubleParsingST
github.com/rschwietzke/1brc-the-first-80-meters.git

Substring

One Less String

Double is Double the Work

Ignore double as longint as Possible

Remove Lambda

Explicit Merging

Mutablility to the Rescue

Less Memory Churn

Open Hashing

Simplify the Map

// https://github.com/mikvor/hashmapTest/blob/master/src/main/java/map/objobj/ObjObjMap.java
public class FastHashMap<K, V> {
    private static final Object FREE_KEY = new Object();
    private Object[] m_data;
...
    public V get( final K key ) {
        int ptr = (key.hashCode() & m_mask) << 1;
        Object k = m_data[ ptr ];

        if ( k == FREE_KEY ) {
            return null;  //end of chain already
        }

        if ( k.hashCode() == key.hashCode() && k.equals( key ) ) {
            return (V) m_data[ ptr + 1 ];
        }

        while ( true ) {
            ptr = (ptr + 2) & m_mask2; //that's next index
            k = m_data[ ptr ];
            if ( k == FREE_KEY ) {
                return null;
            }
            if (k.equals( key )) {
                return (V) m_data[ ptr + 1 ];
            }
        }
    }
...
}
    

org.rschwietzke.devoxxpl24.BRC12_NewMapST

Set instead of Map

Eliminate Slots

public void getPutOrUpdate( final String city, int value ) {
    final int hash = city.hashCode();
    int ptr = hash & m_mask;
    Temperatures k = m_data[ ptr ];

    if ( k == FREE_KEY ) {
        put(new Temperatures(city, value));
        return;
    }

    if ( k.equals( city ) ) {
        k.add(value);
        return;
    }

    while ( true ) {
        ptr = (ptr + 1) & m_mask; //that's next index
        k = m_data[ ptr ];
        if ( k == FREE_KEY ) {
            put(new Temperatures(city, value));
            return;
        }
        if ( k.equals( city ) ) {
            k.add(value);
            return;
        }
    }
}
    

org.rschwietzke.devoxxpl24.BRC13_HardcodedSetST

Heavy Lifting

Approach IO Differently

A Surprise

Enjoy a Treat

Some Cheapish Tuning

Attempting to Save on Number Parsing

Changing Gears

Tuning is Not That Simple Anymore

The Results

Final Thoughts and Numbers

A Few Last Data Tables

Warning, Warning

Your are about to enter an unstable area!