  Choreographies are global descriptions of interactions among concurrent
components, most notably used in the settings of verification and synthesis of
correct-by-construction software. They require a top-down approach: programmers
first write choreographies, and then use them to verify or synthesize their
programs. However, most software does not come with choreographies yet, which
prevents their application. To attack this problem, previous work investigated
choreography extraction, which automatically constructs a choreography that
describes the behaviour of a given set of programs or protocol specifications.
  We propose a new extraction methodology that improves on the state of the
art: we can deal with programs that are equipped with state and internal
computation and time complexity is dramatically better. We also implement this
theory and show that, in spite of its theoretical exponential complexity, it is
usable in practice. We discuss the data structures needed for an efficient
implementation, introduce some optimisations, and perform a systematic
practical evaluation.
