Near-LSPA Performance at MSA Complexity