If i may quote Jan – my understanding was that Prolog does create such choice points and kills them quickly, e.g. when doing an once/1 – but, that such overhead is not significant.
I guess, i am taking this one step further – in my hypothesis – that the decision whether to create a choice point or not – takes cycles as well.