I just did 'strings /dev/urandom > stuff' for 100M. Got it in memory first with untimed grep, then:

    $ time grep -i blah stuff
    bLAH
    blAH

    real	0m7.227s
    user	0m7.194s
    sys	0m0.011s

    $ time LANG=C grep -i blah stuff
    bLAH
    blAH

    real	0m0.486s
    user	0m0.467s
    sys	0m0.016s

So a pretty big difference. My default lang is en_US.utf8.