Faits: Faits: A. A._ a été l'employé de B._ Sàrl depuis 1972 avec une courte interruption en 1977/78. En septembre 1997, il a accédé au poste d'"ingénieur service". Un montant intitulé "ICP" (Incentive Compensation Payment) est versé au début de chaque année aux employés de B._ Sàrl en fonction des résultats de l'année précédente de la société, du collaborateur et de son département. La première partie du formulaire d'évaluation se rapporte aux différents objectifs fixés pour l'année écoulée. Chaque objectif est évalué par une lettre: E [exceeded] signifie que la performance a été supérieure aux objectifs, M [met] qu'elle est satisfaisante et NM [not met] qu'elle est insatisfaisante. La seconde partie du rapport d'évaluation intitulée "JRC" (Job Related Characteristics) contient l'évaluation détaillée des prestations de l'employé. Le rapport d'évaluation de A._ pour l'année 2000 a conclu à une performance insatisfaisante et son supérieur direct lui a demandé une amélioration spécifique pour 2001. L'employé a contesté cette appréciation et refusé de collaborer à améliorer sa performance. Par courrier du 29 janvier 2001, il a résilié son contrat de travail. D'un commun accord, la résiliation a pris effet au 31 mai 2001. Pour les cinq premiers mois de 2001, l'employé a obtenu la note 5, soit la plus mauvaise selon le nouveau système d'évaluation (1 étant la meilleure note). Un montant intitulé "ICP" (Incentive Compensation Payment) est versé au début de chaque année aux employés de B._ Sàrl en fonction des résultats de l'année précédente de la société, du collaborateur et de son département. La première partie du formulaire d'évaluation se rapporte aux différents objectifs fixés pour l'année écoulée. Chaque objectif est évalué par une lettre: E [exceeded] signifie que la performance a été supérieure aux objectifs, M [met] qu'elle est satisfaisante et NM [not met] qu'elle est insatisfaisante. La seconde partie du rapport d'évaluation intitulée "JRC" (Job Related Characteristics) contient l'évaluation détaillée des prestations de l'employé. Le rapport d'évaluation de A._ pour l'année 2000 a conclu à une performance insatisfaisante et son supérieur direct lui a demandé une amélioration spécifique pour 2001. L'employé a contesté cette appréciation et refusé de collaborer à améliorer sa performance. Par courrier du 29 janvier 2001, il a résilié son contrat de travail. D'un commun accord, la résiliation a pris effet au 31 mai 2001. Pour les cinq premiers mois de 2001, l'employé a obtenu la note 5, soit la plus mauvaise selon le nouveau système d'évaluation (1 étant la meilleure note). B. Le 17 juin 2002, A._ a actionné B._ Sàrl devant le Tribunal de la juridiction des prud'hommes à Genève en paiement d'un montant de 30'894 fr. plus intérêts à 5% dès le dépôt de la demande. Ce montant comprend 17'773 fr. d'"ICP" pour l'année 2000, 3'555 fr. de "personal ICP" pour l'année 2000 (20% de 17'773 fr), 7'972 fr. d'"ICP" pour 2001 et 1'594 fr. de "personal ICP" pour 2001 (20% de 7'972 fr.). Lors de l'audience du 10 octobre 2002, le Tribunal a ordonné la production de pièces jusqu'au 15 novembre 2002 et fixé aux parties un délai au 30 novembre 2002 pour déposer leurs éventuels mémoires explicatifs. Par jugement notifié par pli du 28 septembre 2003, le Tribunal a déclaré irrecevables les écritures déposées par le demandeur les 24 septembre et 16 octobre 2002 et l'a débouté de toutes ses conclusions. Le 3 décembre 2003, la Cour d'appel de la juridiction des prud'hommes de Genève a annulé le jugement en tant qu'il déclarait irrecevable l'écriture de l'appelant du 16 octobre 2002 et l'a confirmé pour le surplus. Le 3 décembre 2003, la Cour d'appel de la juridiction des prud'hommes de Genève a annulé le jugement en tant qu'il déclarait irrecevable l'écriture de l'appelant du 16 octobre 2002 et l'a confirmé pour le surplus. C. Se plaignant d'arbitraire dans la constatation des faits, A._ interjette un recours de droit public contre cet arrêt, dont il demande l'annulation. B._ Sàrl conclut au rejet du recours pour autant qu'il soit recevable, sous suite de frais et dépens.