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.

Considérant en droit :
1.
Devant la Cour de justice, les demandeurs ont reproché au Tribunal des baux et loyers de n'avoir pas entendu tous les témoins proposés et de n'avoir pas tenu deux audiences distinctes pour que les parties plaidassent d'abord sur l'offre de preuves et, plus tard seulement, sur le fond.
Ce tribunal a été saisi après l'entrée en vigueur du code de procédure civile unifié, de sorte que contrairement aux affirmations des demandeurs, le droit cantonal antérieur n'est pas en cause.
Selon les art. 150 al. 1 et 152 al. 1 CPC, la preuve n'a pour objet que les faits pertinents et elle ne s'administre que par les moyens adéquats. Les demandeurs ne sont manifestement pas parvenus à expliquer, devant le tribunal puis devant la Cour de justice, en quoi les témoignages qu'ils persistaient à offrir, relatifs à des travaux exécutés dans le bâtiment où se trouvent les locaux en cause, devaient se révéler pertinents au sujet des accords contractuels éventuellement intervenus entre les parties. Ils se plaignent donc à tort d'une violation de leur droit à la preuve. Pour le surplus, devant le tribunal, ils ont eu l'occasion de s'exprimer sur l'appréciation des preuves effectivement administrées et sur les conséquences juridiques des faits qu'ils tenaient pour établis; le droit d'être entendu garanti par l'<ref-law> a donc été respecté. Les critiques développées devant la Cour de justice étaient inconsistantes, de sorte que cette autorité pouvait se dispenser de leur consacrer de longs développements dans son propre arrêt.
2.
Les demandeurs ne contestent guère que le bail à loyer initial ait pris fin à l'expiration de la durée convenue, soit le 31 décembre 2010, conformément à l'<ref-law>. Ils critiquent le délai de préavis d'une année qu'ils devaient observer, selon ce contrat, pour obtenir une prolongation conventionnelle de cinq ans. Ils jugent ce délai excessivement long et donc « insolite ». Il leur incombait pourtant, si ce délai ne leur convenait pas, d'en négocier un plus bref. Ils se réfèrent inutilement à la jurisprudence concernant les clauses insolites qu'une partie contractante insère, le cas échéant, dans des conditions générales qu'elle rédige à l'avance et qu'elle fait conventionnellement incorporer au contrat conclu avec l'autre partie, car le délai de préavis n'était pas prévu dans des conditions de ce genre.
Les demandeurs soutiennent surtout que la défenderesse, en leur adressant au début de l'année 2011 des factures de loyer avec bulletins de versement pour les mois de janvier à mars 2011, a manifesté la volonté de conclure un nouveau contrat de bail à loyer. Au regard du principe de la confiance qui régit l'interprétation des déclarations et manifestations de volonté entre cocontractants (cf. <ref-ruling> consid. 3.2 p. 412; <ref-ruling> consid. 3.3 p. 681), cette thèse est elle aussi inconsistante. Les pourparlers tendant à la conclusion d'un nouveau contrat avaient échoué et les demandeurs avaient saisi l'autorité de conciliation précisément dans le but de faire reconnaître par l'autre partie, ou, si la conciliation échouait, de faire constater par le juge qu'une relation contractuelle se poursuivait. Dans cette situation où le différend des parties était actuel, les demandeurs n'ont pas pu croire de bonne foi que l'envoi de ces documents révélât une volonté de la défenderesse divergeant fondamentalement de la position encore récemment exprimée par elle. La Cour de justice a au contraire pu retenir sans arbitraire, sur la base des déclarations de la défenderesse, que la création et l'envoi de ces documents résultait d'une erreur survenue dans l'administration de la régie.
3.
Aux termes des art. 272 al. 1 et 272b al. 1 CO, le locataire peut demander la prolongation d'un bail de locaux commerciaux pour une durée de six ans au maximum, lorsque la fin du contrat aurait pour lui des conséquences pénibles et que les intérêts du bailleur ne les justifient pas. Dans cette limite de temps, le juge peut accorder une ou deux prolongations.
En tant que les conclusions articulées devant le Tribunal fédéral tendent à une durée de prolongation plus importante que celle réclamée devant les autorités précédentes, elles sont nouvelles, et par conséquent irrecevables au regard de l'<ref-law>. De toute manière, la limite de six ans se calcule à compter de la date à laquelle le contrat prendrait fin ou aurait pris fin sans prolongation; en l'occurrence, elle échet le 31 décembre 2016. Une prolongation de cinq ans à compter de l'arrêt à rendre par le Tribunal fédéral n'entre donc pas en considération.
4.
Le recours se révèle privé de fondement, dans la mesure où les conclusions présentées sont recevables. A titre de parties qui succombent, ses auteurs doivent acquitter l'émolument à percevoir par le Tribunal fédéral et les dépens auxquels leur adverse partie peut prétendre.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté, dans la mesure où il est recevable.
2.
Les demandeurs acquitteront un émolument judiciaire de 6'500 francs.
3.
Les demandeurs verseront une indemnité de 7'500 fr. à la défenderesse, solidairement entre eux, à titre de dépens.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève.
Lausanne, le 21 décembre 2016
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La présidente : Kiss
Le greffier : Thélin