She and Allan by H. Rider Haggard

The old chamberlain, Billali, conducted us back to our camp. As we went he discoursed to me of these Amahagger, of whom it seemed he was himself a developed specimen, one who threw back, perhaps tens of generations, to some superior ancestor who lived before they became debased. In substance he told me that they were a wild and lawless lot who lived amongst ruins or in caves, or some of them in swamp dwellings, in small separate communities, each governed by its petty headman who was generally a priest of their goddess Lulala.

Originally they and the people of Rezu were the same, in times when they worshipped the sun and the moon jointly, but "thousands of years" ago, as he expressed it, they had separated, the Rezuites having gone to dwell to the north of the Great Mountain, whence they continually threatened the Lulalaites whom, had it not been for She-who-commands, they would have destroyed long before. The Rezuites, it seemed, were habitual cannibals, whereas the Lulalaite branch of the Amahagger only practised cannibalism occasionally when by a lucky chance they got hold of strangers. "Such as yourself, Watcher-by-Night, and your companions," he added with meaning. If their crime were discovered, however, Hiya, She-who-commands, punished it by death.