Cookies

@s-panferov I think this handles everything.

cc @reem 
Same `with_capacity` comment as earlier.