What there is quite a bit of is edible greens: dandelions, oxylis, purslane, amaranth, lots of edible green plants and weeds. I can only imagine that our ancestors must of lived off greens.
Modern day studies of wild human tribes in africa that really do live the way people lived hundreds of thousands of years ago, actually mainly subsist on greens. They've been studied, and the researchers have noted that they basically graze on leafy green vegetables all days, lucky to find anything else.
As, the article alluded to, hunger was the norm, pretty much all day, everyday. This day and age, people think of hunger as an anomoly, a problem, something you can't experience for more than a few minutes without going crazy.