Map-reduce implementation for splitting strings
What about the following code. I've improved it by not using regular expressions (except one call of String.split, perhaps you already improved this by your own function split).

private final static char EXPR_VAR = '$';
private final static char EXPR_START = '{';
private final static char EXPR_END = '}';
private final static char EXPR_SPLIT = ',';

public static String replaceVariables(final String expression, final Map&lt;String, String&gt; vars) {
    if (expression == null) {
        throw new IllegalArgumentException("The expression may not be null!");
    }

    if (vars == null) {
        throw new IllegalArgumentException("The vars map may not be null!");
    }

    int firstIndex = expression.indexOf(EXPR_VAR);

    if (firstIndex == -1) {
        // nothing to replace, just return the expression
        return expression;
    }

    final StringBuffer sb = new StringBuffer();
    String tmpExp = expression;
    int lastIndex;
    String group;
    String parts[];

    while (firstIndex != -1) {
        // check if char after '$' is '{'
        if (tmpExp.charAt(firstIndex + 1) != EXPR_START) {
            continue;
        }

        // find ending sign '}'
        lastIndex = tmpExp.indexOf(EXPR_END, firstIndex);

        if (lastIndex &gt; -1) {
            // complete pattern "${...}" found, append previous chars
            sb.append(tmpExp.substring(0, firstIndex));

            // get value inside pattern
            group = tmpExp.substring(firstIndex + 2, lastIndex);

            if (group.indexOf(EXPR_SPLIT) &gt; -1) {
                // we have a pattern like "${xxxxx,xxxxxx}"
                parts = split(group, EXPR_SPLIT);

                if (vars.containsKey(parts[0])) {
                    sb.append(vars.get(parts[0]).substring(0, Integer.valueOf(parts[1])));
                } else {
                    throw new IllegalArgumentException("Key [" + parts[0] + "] not found in variable map!");
                }
            } else {
                // we have a pattern like "${xxxxx}"
                if (vars.containsKey(group)) {
                    sb.append(vars.get(group));
                } else {
                    throw new IllegalArgumentException("Key [" + group + "] not found in variable map!");
                }
            }

            // cut off previous chars from expression
            tmpExp = tmpExp.substring(lastIndex + 1);
        } else {
            // assuming, that if no right parenthesis is found, there is nothing
            // more to replace in this expression. So just get out of here!
            return sb.append(tmpExp).toString();
        }

        // find next pattern
        firstIndex = tmpExp.indexOf(EXPR_VAR);
    }

    // append rest of expression and return it as String
    return sb.append(tmpExp).toString();
}


With the following example values:

final String expression = "Hello! This is a ${1} ${0,2} of foo bla.";
final Map&lt;String, String&gt; vars = new HashMap&lt;&gt;();
vars.put("0", "Foo");
vars.put("1", "funny");


I have a benchmark of (1 million replaces):

// Original (yours):  1872 ms
// Improved (mine):    500 ms


So it's a bit more than three times faster than your implementation.
And the more values like {1,3} are in the input expression, the faster it is in relation:

Input:

final String expression = "${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ";


Benchmark:

// Original:   17455 ms
// Improved:    2855 ms


So, here it is more than six times faster!

Probably, it can be much more improved. But I just wanted to show you a possible direction so far!