La duplication de code est-elle un mal nécessaire en C?

Je suis plutôt nouveau sur C, et je me demande si la duplication de code est un mal nécessaire quand il s'agit d'écrire des structures de données communes et C en général?

Je pourrais essayer d'écrire une implémentation générique pour un hash mappar exemple, mais je trouve toujours le résultat final désordonné. Je pourrais également écrire une implémentation spécialisée juste pour ce cas d'utilisation spécifique, garder le code clair et facile à lire et à déboguer. Cette dernière entraînerait bien sûr une certaine duplication de code.

Les implémentations génériques sont-elles une norme ou écrivez-vous des implémentations différentes pour chaque cas d'utilisation?

C rend difficile l'écriture de code générique. Contrairement à C ++, qui vous offre des modèles et des fonctions virtuelles, C ne dispose que de 3 mécanismes pour écrire du code générique:

1. void* pointeurs
2. Macros de préprocesseur
3. Pointeurs de fonction

void* les pointeurs sont loin d'être idéaux, car vous perdez toute sécurité de type fournie par le compilateur, ce qui peut entraîner un comportement indéfini difficile à déboguer résultant de transtypages de type non valides.

Les macros de préprocesseur ont des inconvénients notables - l'expansion du préprocesseur est fondamentalement juste un mécanisme de recherche / remplacement qui se produit avant la phase de compilation, ce qui peut à nouveau entraîner des erreurs difficiles à déboguer. L'exemple archétypal étant quelque chose comme:, #define add(x) (x+x)où xpeut être incrémenté deux fois si vous appelez add(i++). Vous pouvez écrire du code générique de style modèle entièrement à l'aide de macros C, mais le résultat est vraiment hideux et difficile à maintenir .

Les pointeurs de fonction fournissent un bon moyen d'écrire du code générique, mais malheureusement ils ne vous fournissent pas de généralité de type - ils fournissent simplement la possibilité de polymorphisme au moment de l'exécution (c'est pourquoi, par exemple, la bibliothèque standard qsortnécessite toujours une fonction qui prend void*pointeurs.)

Vous pouvez également implémenter des hiérarchies de classes en C à l'aide de structures, comme cela se fait dans la bibliothèque GLib qui fournit une GObjectclasse de base générique . Mais cela souffre de problèmes similaires à ceux des void*pointeurs, car vous devez toujours vous fier à une conversion manuelle potentiellement dangereuse pour la conversion ascendante et descendante.

Donc oui, C rend difficile l'écriture de code à la fois générique ET sûr / facile à entretenir, ce qui peut malheureusement entraîner une duplication de code. Les grands projets C utilisent souvent des langages de script pour générer du code répétitif pendant le processus de génération.

Je ne peux pas parler pour les autres, mais dans ma propre expérience personnelle avec C, la duplication de code n'a pas été un gros problème. Que cela soit dû à la taille des projets ou à un ensemble d'échantillons charmé, je ne peux pas le dire. Cependant, il y a trois règles empiriques que je suis qui, selon moi, sont applicables. Dans aucun ordre particulier, ils sont ...

1. Écrivez pour ce qui est nécessaire. La généralité peut venir plus tard SI elle est nécessaire.
2. Si une généralité est nécessaire, les pointeurs vides, les pointeurs de fonction et la taille de la structure peuvent être inestimables. La routine qsort (), par exemple, utilise les trois.
3. Donnez du poids à la clarté de votre code.

Il convient de noter que vous n'avez peut-être pas besoin d'une solution entièrement générique pour réduire la duplication de code. Parfois, une refactorisation ordinaire et un peu de généralisation de méthode suffisent.

Lors de la rédaction d'une solution généralisée pour un large public, vous devez considérer:

1. Quelles nouvelles façons le consommateur pourrait-il utiliser votre code et comment les intégrez-vous?
2. Quelles erreurs dois-je détecter? Quelles erreurs ne dois-je pas détecter ?
3. Quelle doit être la robustesse de l'API? Combien de surcharges dois-je fournir?
4. Quelles mesures de sécurité dois-je mettre en place pour que le code ne puisse pas être utilisé à des fins malveillantes?

Eric Lippert a écrit un article entier sur une seule décision de conception dans le code du framework .NET. Dans l'ensemble, il est souvent plus simple de simplement refactoriser.

J'utilise généralement une implémentation générique, comme glib , puis si le casting finit par être trop ennuyeux, faites-lui un petit wrapper spécifique au type. Cependant, beaucoup de transtypages sont attendus en C, tout comme l'utilisation de a void*comme type générique, donc ce qui serait considéré comme "salissant" dans une autre langue est juste typique C. Assez effrayant, cela aura l'air beaucoup plus naturel lorsque vous acquérir plus d'expérience dans la langue.

Votre problème de réutilisabilité n'est pas unique à C. Cependant, il existe des implémentations HashMap excellentes et très réutilisables sur lesquelles vous pouvez baser la vôtre. Celui qui existe depuis une décennie ou deux est en Java: http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

Toutes les collections Java, y compris HashMap, sont en cours de réécriture pour Java 8 pour se débarrasser de l'idée d'un itérateur, et vous obligent à la place à passer une fonction à la collection afin qu'elle puisse itérer en interne. C'est une grande victoire pour l'écriture de code simultané - la collection peut gérer la concurrence en interne afin que le client n'ait pas à le faire. Cela dit, la plupart des programmeurs ne sont pas habitués à passer des pointeurs de fonction. Cela explique bien où HashMap se dirige: http://cr.openjdk.java.net/~briangoetz/lambda/collections-overview.html

La syntaxe de Scala peut rendre difficile la traduction de quelque chose comme ça en C, mais voici un exemple d'une collection qui fonctionne déjà comme les collections Java 8 - immuable par défaut, fournissant diverses méthodes de transformation, utilisant des pointeurs de fonction et d'autres des trucs sympas comme une application partielle: http://www.scala-lang.org/api/current/index.html#scala.collection.Map

Si vous faites beaucoup de choses avec HashMaps et d'autres structures de données plus avancées, vous voudrez peut-être regarder un langage qui les prend en charge.

Revenant à l'idée de duplication de code en général, vous pouvez coder très rapidement en coupant et en collant, mais cela produit un code terrible. Je dirais que c'est acceptable dans le code jetable comme les rapports ponctuels. C'est également OK parfois quand il n'y a pas de code en aval de celui-ci, comme le code d'interface utilisateur qui construit juste un écran dont rien d'autre ne dépend, mais c'est vraiment une zone très grise au mieux.

Je ne pense pas que ce soit trop de simplification de dire que chaque fois que vous vous retrouvez en train de dupliquer du code, vous devez créer une fonction. Les bogues seuls que vous corrigez dans une copie du code et non dans l'autre sont une raison suffisante pour faire une fonction.

Je me demande si la duplication de code est un mal nécessaire quand il s'agit d'écrire des structures de données communes et C en général?

En C, absolument pour moi, comme quelqu'un qui rebondit entre C et C ++. Je reproduis définitivement des choses plus triviales sur une base quotidienne en C qu'en C ++, mais délibérément, et je ne le vois pas nécessairement comme "mal" car il y a au moins quelques avantages pratiques - je pense que c'est une erreur de considérer toutes choses comme strictement "bon" ou "mal" - à peu près tout est une question de compromis. Comprendre clairement ces compromis est la clé pour ne pas éviter des décisions regrettables avec le recul, et le simple fait de qualifier les choses de «bonnes» ou de «mauvaises» ignore généralement toutes ces subtilités.

Bien que le problème ne soit pas unique à C comme d'autres l'ont souligné, il pourrait être considérablement plus exacerbé en C en raison de l'absence de quelque chose de plus élégant que des macros ou des pointeurs vides pour les génériques, de la maladresse de la POO non triviale et du fait que le La bibliothèque standard C ne comprend aucun conteneur. En C ++, une personne implémentant sa propre liste de liens peut provoquer une foule de gens en colère qui demandent pourquoi ils n'utilisent pas la bibliothèque standard, à moins qu'ils ne soient des étudiants. En C, vous invitez une foule en colère si vous ne pouvez pas déployer en toute confiance une élégante implémentation de liste chaînée dans votre sommeil, car un programmeur C devrait souvent au moins être capable de faire ce genre de choses quotidiennement. Il' Ce n'est pas en raison d'une obsession étrange sur les listes chaînées que Linus Torvalds a utilisé l'implémentation de la recherche et de la suppression de SLL en utilisant la double indirection comme critère pour évaluer un programmeur qui comprend la langue et qui a le «bon goût». C'est parce que les programmeurs C pourraient être tenus d'implémenter une telle logique mille fois au cours de leur carrière. Dans ce cas pour C, c'est comme un chef évaluant les compétences d'un nouveau cuisinier en lui faisant juste préparer des œufs pour voir s'il a au moins la maîtrise des choses de base qu'il devra faire tout le temps.

Par exemple, j'ai probablement implémenté cette structure de données de base "liste libre indexée" une douzaine de fois en C localement pour chaque site qui utilise cette stratégie d'allocation (presque toutes mes structures liées pour éviter d'allouer un nœud à la fois et de diviser par deux la mémoire coûts des liens sur 64 bits):

Mais en C, cela prend juste une très petite quantité de code dans reallocun tableau évolutif et en met en commun une partie en utilisant une approche indexée d'une liste libre lors de l'implémentation d'une nouvelle structure de données qui utilise celle-ci.

Maintenant, j'ai la même chose implémentée en C ++ et là je ne l'ai implémentée qu'une seule fois en tant que modèle de classe. Mais c'est une implémentation beaucoup, beaucoup plus complexe du côté C ++ avec des centaines de lignes de code et quelques dépendances externes qui couvrent également des centaines de lignes de code. Et la raison principale pour laquelle c'est beaucoup plus compliqué, c'est parce que je dois le coder contre l'idée qui Tpourrait être n'importe quel type de données possible. Il pourrait lancer à tout moment (sauf lors de sa destruction, ce que je dois faire explicitement comme avec les conteneurs de bibliothèque standard), je devais penser à un alignement correct pour allouer de la mémoire pourT (bien que cela soit heureusement facilité en C ++ 11), il pourrait être non trivialement constructible / destructible (nécessitant le placement de nouvelles invocations de dtor manuelles), je dois ajouter des méthodes dont tout le monde n'aura pas besoin mais certaines choses auront besoin, et je dois ajouter des itérateurs, à la fois des itérateurs mutables et en lecture seule (const), et ainsi de suite.

Les tableaux évolutifs ne sont pas sorciers

En C ++, les gens ont l'impression que std::vectorc'est le travail d'un spécialiste des fusées, optimisé à mort, mais il ne fonctionne pas mieux qu'un tableau C dynamique codé par rapport à un type de données spécifique qui utilise simplement reallocpour augmenter la capacité du tableau lors des refoulements avec un une douzaine de lignes de code. La différence est qu'il faut une implémentation très complexe pour rendre juste une séquence à accès aléatoire évolutive entièrement conforme à la norme, éviter d'appeler des ctors sur des éléments non insérés, sans exception, fournir des itérateurs à accès aléatoire const et non const, type d'utilisation traits pour lever l'ambiguïté des ctors de remplissage des ctors de l'aire de répartition pour certains types intégraux deT, potentiellement traiter les POD différemment en utilisant des traits de type, etc. etc. etc. À ce stade, vous avez en effet besoin d'une implémentation très complexe juste pour créer un tableau dynamique évolutif, mais uniquement parce qu'il essaie de gérer tous les cas d'utilisation possibles jamais imaginables. Du côté positif, vous pouvez obtenir beaucoup de kilométrage de tout cet effort supplémentaire si vous avez vraiment besoin de stocker à la fois des POD et des UDT non triviaux, utilisez des algorithmes génériques basés sur des itérateurs qui fonctionnent sur n'importe quelle structure de données conforme, bénéficier de la gestion des exceptions et du RAII, au moins parfois remplacer std::allocatoravec votre propre allocateur personnalisé, etc. etc. Il est certainement payant dans la bibliothèque standard lorsque vous considérez combien d'avantagesstd::vector a eu sur le monde entier de personnes qui l'ont utilisé, mais c'est pour quelque chose implémenté dans la bibliothèque standard conçue pour cibler les besoins du monde entier.

Implémentations plus simples de gestion de cas d'utilisation très spécifiques

En raison de la gestion de cas d'utilisation très spécifiques avec ma "liste libre indexée", malgré l'implémentation de cette liste gratuite une douzaine de fois sur le côté C et la duplication de code trivial en conséquence, j'ai probablement écrit moins de code total en C pour l'implémenter une douzaine de fois que je devais l'implémenter une seule fois en C ++, et j'ai dû passer moins de temps à maintenir ces dizaines d'implémentations C que je ne devais maintenir cette implémentation C ++. L'une des principales raisons pour lesquelles le côté C est si simple est que je travaille généralement avec des POD en C chaque fois que j'utilise cette technique et je n'ai généralement pas besoin de plus de fonctions que inserteterasesur les sites spécifiques dans lesquels je mets en œuvre localement. Fondamentalement, je peux simplement implémenter le sous-ensemble le plus jeune des fonctionnalités fournies par la version C ++, car je suis libre de faire beaucoup plus d'hypothèses sur ce que je fais et je n'ai pas besoin de la conception lorsque je l'implémente pour une utilisation très spécifique Cas.

Maintenant, la version C ++ est tellement plus agréable et sécurisée à utiliser, mais c'était toujours un PITA majeur à implémenter et à rendre compatible avec les itérateurs à l'exception des bidirectionnels et des exceptions, par exemple, de manière à proposer une implémentation générale et réutilisable qui coûte probablement dans ce cas, plus de temps qu'il n'en fait. Et une grande partie de ce coût de mise en œuvre d'une manière généralisée est gaspillée non seulement au départ, mais à plusieurs reprises sous la forme de choses comme des temps de construction plus élevés payés à plusieurs reprises chaque jour.

Pas une attaque contre C ++!

Mais ce n'est pas une attaque contre C ++ parce que j'adore C ++, mais en ce qui concerne les structures de données, je suis venu à privilégier C ++ principalement pour les structures de données vraiment non triviales dans lesquelles je veux passer beaucoup de temps d'avance à mettre en œuvre dans d'une manière très généralisée, rendre l'exception-sûr contre tous les types possibles de T, rendre conforme aux normes et itérable, etc., où ce type de coût initial est vraiment rentable sous la forme d'une tonne de kilométrage.

Pourtant, cela favorise également un état d'esprit de conception très différent. En C ++ si je veux faire un Octree pour la détection de collision, j'ai tendance à vouloir le généraliser au nième degré. Je ne veux pas simplement lui faire stocker des maillages triangulaires indexés. Pourquoi devrais-je le limiter à un seul type de données avec lequel il peut fonctionner lorsque j'ai un mécanisme de génération de code super puissant à portée de main qui élimine toutes les pénalités d'abstraction lors de l'exécution? Je veux qu'il stocke des sphères procédurales, des cubes, des voxels, des surfaces NURB, des nuages ​​de points, etc., etc., etc. Je pourrais même ne pas vouloir le limiter à la détection de collision - que diriez-vous du lancer de rayons, du prélèvement, etc.? C ++ donne au début un aspect "sorta facile" pour généraliser une structure de données au nième degré. Et c'est ainsi que j'avais l'habitude de concevoir de tels index spatiaux en C ++. J'ai essayé de les concevoir pour gérer les besoins de la faim dans le monde entier, et ce que j'ai obtenu en échange était généralement un "cric de tous les métiers" avec un code extrêmement complexe pour le mettre en balance avec tous les cas d'utilisation possibles imaginables.

Curieusement, j'ai obtenu plus de réutilisation des index spatiaux que j'ai mis en œuvre en C au fil des ans, et sans faute de C ++, mais seulement le mien dans ce que le langage me tente de faire. Lorsque je code quelque chose comme un octree en C, j'ai tendance à simplement le faire fonctionner avec des points et à en être content, car le langage rend trop difficile même d'essayer de le généraliser au nième degré. Mais en raison de ces tendances, j'ai eu tendance à concevoir des choses au fil des ans qui sont en fait plus efficaces et fiables et vraiment bien adaptées à certaines tâches à accomplir, car elles ne se soucient pas d'être générales au nième degré. Ils deviennent des as dans une catégorie spécialisée au lieu d'un cric de tous les métiers. Encore une fois, cela ne vient pas de la faute de C ++, mais simplement des tendances humaines que j'ai lorsque je l'utilise par opposition à C.

Mais de toute façon, j'aime les deux langues mais il y a des tendances différentes. En CI ont tendance à ne pas généraliser suffisamment. En C ++, j'ai tendance à trop généraliser. Utiliser les deux m'a en quelque sorte aidé à m'équilibrer.

Les implémentations génériques sont-elles une norme ou écrivez-vous des implémentations différentes pour chaque cas d'utilisation?

Pour des choses triviales comme des listes indexées 32 bits à liaison unique utilisant des nœuds d'un tableau ou un tableau qui se réalloue (équivalent analogique de std::vectorC ++) ou, disons, un octree qui stocke simplement des points et vise à ne rien faire de plus, je ne le fais pas '' t prendre la peine de généraliser au point de stocker tout type de données. Je les implémente pour stocker un type de données spécifique (bien qu'il puisse être abstrait et utiliser des pointeurs de fonction dans certains cas, mais au moins plus spécifiques que le typage canard avec polymorphisme statique).

Et je suis parfaitement satisfait d'un peu de redondance dans ces cas, à condition que je le teste à fond. Si je ne fais pas de test unitaire, alors la redondance commence à se sentir beaucoup plus mal à l'aise, car vous pourriez avoir du code redondant qui pourrait être la duplication d'erreurs, par exemple, même si le type de code que vous écrivez ne nécessitera probablement jamais de modifications de conception, il pourrait encore avoir besoin de modifications car il est cassé. J'ai tendance à écrire des tests unitaires plus approfondis pour le code C que j'écris comme raison.

Pour les choses non triviales, c'est généralement lorsque j'atteins C ++, mais si je l'implémentais en C, j'envisagerais d'utiliser uniquement des void*pointeurs, j'accepterais peut-être une taille de type pour savoir combien de mémoire allouer pour chaque élément, et éventuellement copy/destroydes pointeurs de fonction pour copier en profondeur et détruire les données si elles ne sont pas trivialement constructibles / destructibles. La plupart du temps, je ne dérange pas et n'utilise pas autant de C pour créer les structures de données et les algorithmes les plus complexes.

Si vous utilisez une structure de données assez fréquemment avec un type de données particulier, vous pouvez également envelopper une version de type sécurisé sur une version qui fonctionne uniquement avec des bits et des octets et des pointeurs de fonction et void*, par exemple, pour réimposer la sécurité de type via l'encapsuleur C.

Je pourrais essayer d'écrire une implémentation générique pour une carte de hachage par exemple, mais je trouve toujours le résultat final compliqué. Je pourrais également écrire une implémentation spécialisée juste pour ce cas d'utilisation spécifique, garder le code clair et facile à lire et à déboguer. Cette dernière entraînerait bien sûr une certaine duplication de code.

Les tables de hachage sont un peu douteuses car leur mise en œuvre peut être triviale ou très complexe en fonction de la complexité de vos besoins en termes de hachages, de retouches, si vous avez besoin de faire croître automatiquement la table de manière implicite ou d'anticiper la taille de la table dans avance, que vous utilisiez l'adressage ouvert ou le chaînage séparé, etc. Mais une chose à garder à l'esprit est que si vous avez parfaitement adapté une table de hachage aux besoins d'un site spécifique, sa mise en œuvre ne sera souvent pas si complexe et souvent gagnée. ne soyez pas si redondant lorsqu'il est conçu précisément pour ces besoins. C'est du moins l'excuse que je me donne si j'implémente quelque chose localement. Sinon, vous pouvez simplement utiliser la méthode décrite ci-dessus avec void*des pointeurs de fonction et pour copier / détruire des choses et les généraliser.

Souvent, il ne faut pas beaucoup d'efforts ou beaucoup de code pour battre une structure de données très généralisée si votre alternative est extrêmement étroitement applicable à votre cas d'utilisation exact. Par exemple, il est absolument trivial de battre les performances de l'utilisation mallocpour chaque nœud (par opposition à la mise en commun d'un tas de mémoire pour de nombreux nœuds) une fois pour toutes avec du code que vous n'avez jamais à revoir pour un cas d'utilisation très, très exact même lorsque de nouvelles implémentations de mallocsortir. Cela peut prendre toute une vie pour le battre et coder non moins complexe que vous devez consacrer une grande partie de votre vie à le maintenir et à le mettre à jour si vous voulez correspondre à sa généralité.

Comme autre exemple, j'ai souvent trouvé qu'il était extrêmement facile de mettre en œuvre des solutions 10 fois plus rapides ou plus que les solutions VFX proposées par Pixar ou Dreamworks. Je peux le faire dans mon sommeil. Mais ce n'est pas parce que mes implémentations sont supérieures - loin, loin de là. Ils sont carrément inférieurs pour la plupart des gens. Ils ne sont supérieurs que pour mes cas d'utilisation très, très spécifiques. Mes versions sont de loin, beaucoup moins généralement applicables que celles de Pixar ou Dreamwork. C'est une comparaison ridiculement injuste car leurs solutions sont absolument brillantes par rapport à mes solutions stupides, mais c'est un peu le point. La comparaison n'a pas besoin d'être juste. Si vous n'avez besoin que de quelques choses très spécifiques, vous n'avez pas besoin de faire en sorte qu'une structure de données gère une liste interminable de choses dont vous n'avez pas besoin.

Bits et octets homogènes

Une chose à exploiter en C car il a un tel manque inhérent de sécurité de type est l'idée de stocker les choses de manière homogène en fonction des caractéristiques des bits et des octets. Il y a plus de flou à la suite entre l'allocateur de mémoire et la structure de données.

Mais stocker un tas de choses de taille variable, ou même des choses qui pourraient simplement être de taille variable, comme un polymorphe Doget Cat, est difficile à faire efficacement. Vous ne pouvez pas partir du principe qu'ils peuvent être de taille variable et les stocker de manière contiguë dans un simple conteneur à accès aléatoire car la foulée pour passer d'un élément au suivant peut être différente. Par conséquent, pour stocker une liste qui contient à la fois des chiens et des chats, vous devrez peut-être utiliser 3 instances de structure de données / allocateur distinctes (une pour les chiens, une pour les chats et une pour une liste polymorphe de pointeurs de base ou de pointeurs intelligents, ou pire) , allouez chaque chien et chaque chat à un allocateur à usage général et répartissez-les dans toute la mémoire), ce qui coûte cher et entraîne sa part de ratés de cache multipliés.

Ainsi, une stratégie à utiliser en C, même si elle se traduit par une richesse et une sécurité de type réduites, consiste à généraliser au niveau des bits et des octets. Vous pourrez peut-être supposer cela Dogset Catsnécessiter le même nombre de bits et d'octets, avoir les mêmes champs, le même pointeur vers une table de pointeurs de fonction. Mais en échange, vous pouvez alors coder moins de structures de données, mais tout aussi important, stocker toutes ces choses de manière efficace et contiguë. Dans ce cas, vous traitez les chiens et les chats comme des unions analogiques (ou vous pourriez simplement utiliser une union).

Et cela a un coût énorme pour taper la sécurité. S'il y a une chose qui me manque plus que toute autre chose en C, c'est la sécurité de type. Il se rapproche du niveau d'assemblage où les structures indiquent simplement la quantité de mémoire allouée et la façon dont chaque champ de données est aligné. Mais c'est en fait ma principale raison d'utiliser C. Si vous essayez vraiment de contrôler les dispositions de la mémoire et où tout est alloué et où tout est stocké les uns par rapport aux autres, il est souvent utile de penser aux choses au niveau des bits et octets et la quantité de bits et d'octets dont vous avez besoin pour résoudre un problème particulier. Là, la stupidité du système de type C peut en fait devenir bénéfique plutôt qu'un handicap. En règle générale, cela aboutira à beaucoup moins de types de données à traiter,

Duplication illusoire / apparente

Maintenant, j'utilise la «duplication» au sens large pour des choses qui ne sont peut-être même pas redondantes. J'ai vu des gens distinguer des termes comme la duplication "incidente / apparente" de "la duplication réelle". À mon avis, il n'y a pas de distinction aussi claire dans de nombreux cas. Je trouve que la distinction ressemble plus à «l'unicité potentielle» par rapport à la «duplication potentielle» et elle peut aller dans les deux sens. Cela dépend souvent de la façon dont vous souhaitez que vos conceptions et implémentations évoluent et de la façon dont elles seront parfaitement adaptées à un cas d'utilisation spécifique. Mais j'ai souvent constaté que ce qui pourrait sembler être une duplication de code s'avérait ne plus être redondant après plusieurs itérations d'améliorations.

Prenez une implémentation simple de tableau évolutif en utilisant reallocl'équivalent analogique de std::vector<int>. Au départ, il pourrait être redondant avec, disons, l'utilisation std::vector<int>en C ++. Mais vous pouvez constater, en mesurant, qu'il peut être avantageux de préallouer 64 octets à l'avance pour permettre l'insertion de seize entiers 32 bits sans nécessiter d'allocation de segment. Maintenant, ce n'est plus redondant, du moins pas avec std::vector<int>. Et puis vous pourriez dire: «Mais je pourrais simplement généraliser ceci à un nouveau SmallVector<int, 16>, et vous pourriez. Mais alors disons que vous trouvez que c'est utile parce que ce sont pour de très petites baies de courte durée de vie pour quadrupler la capacité de la baie sur les allocations de tas au lieu de augmentant de 1,5 (à peu près le montant que beaucoupvectorimplémentations) tout en partant de l'hypothèse que la capacité de la baie est toujours une puissance de deux. Maintenant, votre conteneur est vraiment différent, et il n'y a probablement pas de conteneur comme celui-ci. Et peut-être pourriez-vous essayer de généraliser de tels comportements en ajoutant de plus en plus de paramètres de modèle pour personnaliser la pré-allocation plus lourde, personnaliser le comportement de réallocation, etc. etc., mais à ce stade, vous pourriez trouver quelque chose de vraiment difficile à utiliser par rapport à une douzaine de lignes de C code.

Et vous pourriez même atteindre un point où vous avez besoin d'une structure de données qui alloue de la mémoire alignée et rembourrée 256 bits, stockant exclusivement des POD pour les instructions AVX 256, préalloue 128 octets pour éviter les allocations de tas pour les petites tailles d'entrée courantes, double de capacité lorsque plein, et permet des remplacements sûrs des éléments de fin dépassant la taille du tableau mais pas la capacité du tableau. À ce stade, si vous essayez toujours de généraliser une solution pour éviter de dupliquer une petite quantité de code C, que les dieux de la programmation aient pitié de votre âme.

Il y a donc aussi des moments comme celui-ci où ce qui au départ semble redondant commence à se développer, à mesure que vous personnalisez une solution pour mieux et mieux adapter un certain cas d'utilisation, en quelque chose de tout à fait unique et pas du tout redondant. Mais ce n'est que pour des choses où vous pouvez vous permettre de les adapter parfaitement à un cas d'utilisation spécifique. Parfois, nous avons juste besoin d'une chose «décente» qui est généralisée pour notre objectif, et là je profite le plus de structures de données très généralisées. Mais pour des choses exceptionnelles parfaitement conçues pour un cas d'utilisation particulier, l'idée de «usage général» et «parfaitement adapté à mon usage» commence à devenir trop incompatible.

POD et primitifs

Maintenant en C, je trouve souvent des excuses pour stocker les POD et surtout les primitives dans les structures de données chaque fois que possible. Cela peut sembler un anti-modèle, mais je l'ai trouvé utile par inadvertance pour améliorer la maintenabilité du code par rapport aux types de choses que je faisais plus souvent en C ++.

Un exemple simple est l'internement de chaînes courtes (comme c'est généralement le cas avec les chaînes utilisées pour les clés de recherche - elles ont tendance à être très courtes). Pourquoi prendre la peine de traiter toutes ces chaînes de longueur variable dont les tailles varient au moment de l'exécution, ce qui implique une construction et une destruction non triviales (car nous pourrions avoir besoin d'allouer des tas et de les libérer)? Que diriez-vous de simplement stocker ces choses dans une structure de données centrale, comme un trie thread-safe ou une table de hachage conçue uniquement pour l'internement de chaînes, puis faites référence à ces chaînes avec un ancien int32_tou:

struct IternedString 
{
    int32_t index;
};

... dans nos tables de hachage, arbres rouge-noir, listes à sauter, etc., si nous n'avons pas besoin de tri lexicographique? Maintenant, toutes nos autres structures de données que nous avons codées pour fonctionner avec des entiers 32 bits peuvent désormais stocker ces clés de chaîne internes qui ne sont en fait que 32 bits ints. Et j'ai trouvé dans mes cas d'utilisation au moins (peut-être juste mon domaine puisque je travaille dans des domaines comme le raytracing, le traitement de maillage, le traitement d'image, les systèmes de particules, la liaison aux langages de script, les implémentations de kit GUI multithread de bas niveau, etc. - des choses de bas niveau mais pas aussi bas qu'un OS), que le code se trouve par hasard devenir plus efficace et plus simple en stockant simplement des indices pour des choses comme ça. Cela fait que je travaille souvent, disons 75% du temps, avec juste int32_tetfloat32 dans mes structures de données non triviales, ou tout simplement stocker des choses qui sont de la même taille (presque toujours 32 bits).

Et naturellement, si cela s'applique à votre cas, vous pouvez éviter d'avoir un certain nombre d'implémentations de structure de données pour différents types de données, car vous travaillerez avec si peu en premier lieu.

Test et fiabilité

Une dernière chose que j'offrirais, et ce n'est peut-être pas pour tout le monde, est de favoriser l'écriture de tests pour ces structures de données. Faites-les vraiment bons à quelque chose. Assurez-vous qu'ils sont ultra fiables.

Dans certains cas, la duplication de code mineure devient beaucoup plus tolérable, car la duplication de code n'est qu'une charge de maintenance si vous devez apporter des modifications en cascade au code dupliqué. Vous éliminez l'une des principales raisons pour lesquelles ce code redondant change en vous assurant qu'il est ultra fiable et vraiment bien adapté à ce qu'il tente de faire.

Mon sens de l'esthétique a changé au fil des ans. Je ne suis plus irrité parce que je vois une bibliothèque implémenter un produit scalaire ou une logique SLL triviale qui est déjà implémentée dans une autre. Je ne m'énerve que lorsque les choses sont mal testées et peu fiables, et j'ai trouvé cet état d'esprit beaucoup plus productif. J'ai véritablement traité des bases de code qui dupliquaient les bogues via du code dupliqué, et j'ai vu les pires cas de codage copier-coller faire ce qui aurait dû être un changement trivial à un endroit central se transformer en un changement en cascade sujet à des erreurs pour beaucoup. Pourtant, la plupart du temps, c'était le résultat de tests médiocres, du code qui n'était pas devenu fiable et bon dans ce qu'il faisait en premier lieu. Avant, quand je travaillais dans des bases de code héritées du buggy, mon esprit a associé toutes les formes de duplication de code comme ayant une très forte probabilité de duplication des bogues et nécessitant des changements en cascade. Pourtant, une bibliothèque miniature qui fait une chose extrêmement bien et de manière fiable ne trouvera que très peu de raisons de changer à l'avenir, même si elle a un code redondant ici et là. Mes priorités n'étaient pas à l'époque lorsque la duplication m'irritait plus que la mauvaise qualité et le manque de tests. Ces dernières choses devraient être la priorité absolue.

Duplication de code pour le minimalisme?

C'est une drôle de pensée qui m'est venue à l'esprit, mais considérons un cas où nous pourrions rencontrer une bibliothèque C et C ++ qui fait à peu près la même chose: les deux ont à peu près la même fonctionnalité, la même quantité de gestion des erreurs, on n'est pas significativement plus efficaces les uns que les autres, etc. Et surtout, les deux sont mis en œuvre avec compétence, bien testés et fiables. Malheureusement, je dois parler hypothétiquement ici car je n'ai jamais rien trouvé de proche d'une comparaison côte à côte parfaite. Mais les choses les plus proches que j'ai jamais trouvées pour cette comparaison côte à côte avaient souvent la bibliothèque C étant beaucoup, beaucoup plus petite que l'équivalent C ++ (parfois 1 / 10e de sa taille de code).

Et je pense que la raison en est que, encore une fois, pour résoudre un problème d'une manière générale qui gère la plus large gamme de cas d'utilisation au lieu d'un cas d'utilisation exact, il peut nécessiter des centaines à des milliers de lignes de code, alors que ce dernier ne peut nécessiter une douzaine. Malgré la redondance, et malgré le fait que la bibliothèque standard C soit épouvantable lorsqu'il s'agit de fournir des structures de données standard, elle finit souvent par produire moins de code entre les mains de l'homme pour résoudre les mêmes problèmes, et je pense que cela est principalement dû aux différences de tendances humaines entre ces deux langues. L'un favorise la résolution de problèmes par rapport à un cas d'utilisation très spécifique, l'autre tend à promouvoir des solutions plus abstraites et génériques par rapport à la plus large gamme de cas d'utilisation, mais le résultat final de ceux-ci ne fonctionne pas.

L'autre jour, je regardais le raytracer de quelqu'un sur github et il a été implémenté en C ++ et nécessitait donc beaucoup de code pour un raytracer jouet. Et je n'ai pas passé beaucoup de temps à regarder le code, mais il y avait une cargaison de structures à usage général là-dedans qui géraient bien plus que ce dont un raytracer aurait besoin. Et je reconnais ce style de codage parce que j'utilisais C ++ de la même manière dans une sorte de mode super ascendant, en me concentrant sur la création d'une bibliothèque complète de structures de données très générales qui vont bien au-delà de l'immédiat problème à la main, puis s'attaquer au problème réel en second. Mais alors que ces structures générales peuvent éliminer une certaine redondance ici et là et profiter de beaucoup de réutilisation dans de nouveaux contextes, en échange, ils gonflent énormément le projet en échangeant un peu de redondance avec une cargaison de code / fonctionnalité inutile, et cette dernière n'est pas nécessairement plus facile à maintenir que la première. Au contraire, je trouve souvent plus difficile à maintenir, car il est difficile de maintenir une conception de quelque chose de général qui doit équilibrer les décisions de conception par rapport à la plus large gamme de besoins possible.