Faits : A. Dès le 16 décembre 2005, H.X._ et F.X._ ont pris à bail un magasin de 29 m2 et deux dépôts de 5 et 6 m2 au rez-de-chaussée d'un bâtiment du centre de Genève, afin d'y exploiter un commerce de chaussures. Conclu le 24 août précédent, le contrat devait prendre fin le 31 décembre 2010 sans résiliation préalable. Il était toutefois prévu que les locataires pourraient en obtenir la prolongation pour une durée fixe de cinq ans échéant le 31 décembre 2015; cette option devait être exercée au plus tard le 31 décembre 2009 et la bailleresse Z._ SA se réservait l'adaptation du loyer aux conditions du marché. Le loyer convenu était échelonné; il fut porté à 8'941 fr. par mois dès le 1er janvier 2009. Dès le 23 mars 2010, les locataires ont exprimé leur souhait d'obtenir une prolongation du contrat. La bailleresse, par l'intermédiaire de sa régie, a fait état d'une valeur locative actuelle de 7'000 fr. par mètre carré et par année; elle a invité les locataires à lui soumettre une proposition écrite avant le 30 juin. Le 26 juin 2010, les locataires ont déclaré qu'ils consentiraient, faute d'autre choix, un loyer mensuel de 16'916 fr. correspondant à cette valeur, pour autant qu'il fût fixé pour dix ans. Le 30 septembre, la bailleresse a fait savoir que la proposition demeurait à l'étude mais qu'un tiers avait présenté une offre plus élevée. Enfin, le 26 octobre, la bailleresse a communiqué qu'elle ne souhaitait pas accorder de nouveau bail aux locataires et que l'état des lieux à leur sortie des locaux était fixé au 3 janvier 2011. Au début de l'année 2011, la régie a établi et envoyé aux locataires des factures de loyer avec bulletins de versement pour les mois de janvier à mars 2011. La bailleresse a par la suite expliqué qu'il s'agissait d'une erreur résultant d'une administration automatisée. B. Dans l'intervalle, le 29 octobre 2010, les locataires avaient saisi l'autorité de conciliation compétente et ils ont plus tard, le 20 octobre 2011, introduit une demande en justice contre la bailleresse devant le Tribunal des baux et loyers du canton de Genève. Le tribunal était requis de constater que les parties demeuraient liées par un contrat de bail à loyer; à titre subsidiaire, les demandeurs réclamaient une prolongation judiciaire du contrat initial pour une durée de cinq ans. La défenderesse a conclu au rejet de l'action. Le tribunal a interrogé les parties et divers témoins. Il a refusé de convoquer neuf autres témoins encore proposés par les demandeurs. Ceux-ci ont soulevé un incident à ce sujet. Le tribunal a convoqué les parties pour plaider simultanément sur l'incident et sur le fond. Il s'est enfin prononcé le 18 septembre 2015; il a intégralement rejeté l'action. La Chambre des baux et loyers de la Cour de justice a statué le 6 juin 2016 sur l'appel des demandeurs. Elle leur a donné partiellement gain de cause en ce sens que le contrat initial est prolongé d'une durée unique de deux ans et demi, d'ores et déjà échue le 30 juin 2013. C. Agissant par la voie du recours en matière civile, les demandeurs requièrent le Tribunal fédéral, à titre principal, de constater que les locaux par eux occupés à Genève sont l'objet d'un bail commercial valable entre les parties; à titre subsidiaire, ils réclament la prolongation judiciaire du contrat initial pour une durée de cinq ans à compter de l'arrêt qui terminera l'instance. La défenderesse conclut au rejet du recours, dans la mesure où celui-ci est recevable.