FaceUniqueIdBuilder.cc

// -*- tab-width: 2; indent-tabs-mode: nil; coding: utf-8-with-signature -*-
//-----------------------------------------------------------------------------
// Copyright 2000-2026 CEA (www.cea.fr) IFPEN (www.ifpenergiesnouvelles.com)
// See the top-level COPYRIGHT file for details.
// SPDX-License-Identifier: Apache-2.0
//-----------------------------------------------------------------------------
/*---------------------------------------------------------------------------*/
/* FaceUniqueIdBuilder.cc                                      (C) 2000-2026 */
/*                                                                           */
/* Construction of unique face identifiers.                                  */
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
#include "arcane/utils/PlatformUtils.h"
#include "arcane/utils/ScopedPtr.h"
#include "arcane/utils/ITraceMng.h"
#include "arcane/utils/OStringStream.h"
#include "arcane/utils/CheckedConvert.h"
 
#include "arcane/core/IMeshUniqueIdMng.h"
#include "arcane/core/IParallelExchanger.h"
#include "arcane/core/IParallelMng.h"
#include "arcane/core/IParallelNonBlockingCollective.h"
#include "arcane/core/ISerializeMessage.h"
#include "arcane/core/ISerializer.h"
#include "arcane/core/ParallelMngUtils.h"
 
#include "arcane/mesh/DynamicMesh.h"
#include "arcane/mesh/OneMeshItemAdder.h"
#include "arcane/mesh/GhostLayerBuilder.h"
#include "arcane/mesh/FaceUniqueIdBuilder.h"
#include "arcane/mesh/ItemTools.h"
#include "arcane/mesh/ItemsOwnerBuilder.h"
#include "arcane/mesh/internal/Int64AllToAll.h"
 
#include <unordered_set>
#include <algorithm>
#include <cstdint>
#include <fstream>
#include <utility>
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
namespace Arcane::mesh
{
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
extern "C++" void
_computeFaceUniqueIdVersion3(DynamicMesh* mesh);
extern "C++" void
_computeFaceUniqueIdVersion5(DynamicMesh* mesh);
extern "C++" void
arcaneComputeCartesianFaceUniqueId(DynamicMesh* mesh);
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
FaceUniqueIdBuilder::
FaceUniqueIdBuilder(DynamicMeshIncrementalBuilder* mesh_builder)
: TraceAccessor(mesh_builder->mesh()->traceMng())
, m_mesh(mesh_builder->mesh())
, m_mesh_builder(mesh_builder)
{
  // ARCANE_DISTRIBUTED_FACE_NUMBERING=1 distributes the computation of the face
  // numbering of version 1 over the ranks instead of performing it on each.
  auto distributed = Convert::Type<Int32>::tryParseFromEnvironment("ARCANE_DISTRIBUTED_FACE_NUMBERING", true);
  m_is_v1_distributed = distributed && distributed.value() != 0;
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
void FaceUniqueIdBuilder::
computeFacesUniqueIds()
{
  IParallelMng* pm = m_mesh->parallelMng();
  Real begin_time = platform::getRealTime();
  Integer face_version = m_mesh->meshUniqueIdMng()->faceBuilderVersion();
  bool is_parallel = pm->isParallel();
  info() << "Using version=" << face_version << " to compute faces unique ids"
         << " mesh=" << m_mesh->name() << " is_parallel=" << is_parallel;
 
  if (face_version > 5 || face_version < 0)
    ARCANE_FATAL("Invalid value '{0}' for compute face unique ids versions: v>=0 && v<=6", face_version);
 
  if (face_version == 5)
    _computeFaceUniqueIdVersion5(m_mesh);
  else if (face_version == 4)
    arcaneComputeCartesianFaceUniqueId(m_mesh);
  else if (face_version == 3)
    _computeFaceUniqueIdVersion3(m_mesh);
  else if (face_version == 0) {
    info() << "No face renumbering";
  }
  else {
    // Version 1 or 2
    if (is_parallel) {
      if (face_version == 2) {
        //NOT YET BY DEFAULT
        info() << "Use new mesh init in FaceUniqueIdBuilder";
        _computeFacesUniqueIdsParallelV2();
      }
      else {
        // Default version.
        _computeFacesUniqueIdsParallelV1();
      }
    }
    else {
      _computeFacesUniqueIdsSequential();
    }
  }
 
  Real end_time = platform::getRealTime();
  Real diff = (Real)(end_time - begin_time);
  info() << "TIME to compute face unique ids=" << diff;
 
  if (arcaneIsCheck())
    _checkNoDuplicate();
 
  ItemInternalMap& faces_map = m_mesh->facesMap();
 
  // We must re-index #m_faces_map because the uniqueId() of the
  // faces have been modified
  if (face_version != 0)
    m_mesh->faceFamily()->notifyItemsUniqueIdChanged();
 
  bool is_verbose = m_mesh_builder->isVerbose();
  if (is_verbose) {
    info() << "NEW FACES_MAP after re-indexing";
    faces_map.eachItem([&](Item face) {
      info() << "Face uid=" << face.uniqueId() << " lid=" << face.localId();
    });
  }
  // With version 0 or 5, the owners are not positioned
  // We must do it now
  if (face_version == 0 || face_version == 5) {
    ItemsOwnerBuilder owner_builder(m_mesh);
    owner_builder.computeFacesOwner();
  }
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_checkNoDuplicate()
{
  info() << "Check no duplicate face uniqueId";
  ItemInternalMap& faces_map = m_mesh->facesMap();
  std::unordered_set<Int64> checked_faces_map;
  faces_map.eachItem([&](Item face) {
    ItemUniqueId uid = face.uniqueId();
    auto p = checked_faces_map.find(uid);
    if (p != checked_faces_map.end()) {
      pwarning() << "Duplicate Face UniqueId=" << uid;
      ARCANE_FATAL("Duplicate Face uniqueId={0}", uid);
    }
    checked_faces_map.insert(uid);
  });
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
class T_CellFaceInfo
{
 public:
 
  T_CellFaceInfo(Int64 uid, Integer nb_back_face, Integer nb_true_boundary_face)
  : m_unique_id(uid)
  , m_nb_back_face(nb_back_face)
  , m_nb_true_boundary_face(nb_true_boundary_face)
  {
  }
 
  T_CellFaceInfo()
  : m_unique_id(NULL_ITEM_ID)
  , m_nb_back_face(0)
  , m_nb_true_boundary_face(0)
  {
  }
 
 public:
 
  bool operator<(const T_CellFaceInfo& ci) const
  {
    return m_unique_id < ci.m_unique_id;
  }
 
 public:
 
  Int64 m_unique_id;
  Int64 m_nb_back_face;
  Int64 m_nb_true_boundary_face;
};
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
namespace
{

inline Int32
_bucketOfHash(Int64 key, Int32 nb_rank)
{
  // splitmix64 finaliser: equal keys meet, consecutive ones do not pile up.
  uint64_t h = static_cast<uint64_t>(key);
  h = (h ^ (h >> 30)) * 0xbf58476d1ce4e5b9ULL;
  h = (h ^ (h >> 27)) * 0x94d049bb133111ebULL;
  h ^= h >> 31;
  return static_cast<Int32>(h % static_cast<uint64_t>(nb_rank));
}

UniqueArray<Int64>
_sliceBounds(IParallelMng* pm, ConstArrayView<Int64> keys, Int64 g_lo, Int64 g_hi)
{
  const Int32 nb_rank = pm->commSize();
  // The more buckets, the better the balance and the larger the sum over the
  // ranks (nb_bucket_per_slice * nb_rank Int64).
  const Int64 nb_bucket_per_slice = 4;
 
  struct Bucket
  {
    Int64 lo;
    Int64 width;
    Int64 count; 
  };
  auto split = [](Array<Bucket>& out, Int64 lo, Int64 width, Int64 nb) {
    const Int64 w = (width - 1) / nb + 1;
    for (Int64 a = lo; a < lo + width; a += w)
      out.add(Bucket{ a, std::min(w, lo + width - a), -1 });
  };
  // Counts the keys of the buckets not counted yet, summed over the ranks.
  auto count = [&](Array<Bucket>& buckets) {
    UniqueArray<Int32> todo;
    for (Int32 i = 0; i < buckets.size(); ++i) {
      if (buckets[i].count < 0)
        todo.add(i);
    }
    UniqueArray<Int64> c(todo.size());
    const Int64* k = keys.data();
    const Int64* k_end = k + keys.size();
    for (Int32 i = 0; i < todo.size(); ++i) {
      const Bucket& b = buckets[todo[i]];
      c[i] = std::lower_bound(k, k_end, b.lo + b.width) - std::lower_bound(k, k_end, b.lo);
    }
    pm->reduce(Parallel::ReduceSum, c);
    for (Int32 i = 0; i < todo.size(); ++i)
      buckets[todo[i]].count = c[i];
  };
 
  UniqueArray<Bucket> buckets;
  split(buckets, g_lo, g_hi - g_lo + 1, nb_bucket_per_slice * nb_rank);
  count(buckets);
  Int64 total = 0;
  for (const Bucket& b : buckets)
    total += b.count;
 
  // A bucket holding more than a slice's share is cut again, into as many
  // buckets per share as at first. Every rank holds the same histogram, so
  // every rank cuts the same buckets.
  for (;;) {
    UniqueArray<Bucket> next;
    bool is_cut = false;
    for (const Bucket& b : buckets) {
      if (b.width > 1 && b.count * nb_rank > total) {
        split(next, b.lo, b.width, (nb_bucket_per_slice * b.count * nb_rank + total - 1) / total);
        is_cut = true;
      }
      else
        next.add(b);
    }
    if (!is_cut)
      break;
    buckets = next;
    count(buckets);
  }
 
  UniqueArray<Int64> bounds(nb_rank + 1, g_hi + 1);
  bounds[0] = g_lo;
  Int32 last = 0;
  Int64 before = 0;
  for (const Bucket& b : buckets) {
    const Int32 s = static_cast<Int32>(std::min<Int64>(nb_rank - 1, before * nb_rank / total));
    for (Int32 t = last + 1; t <= s; ++t)
      bounds[t] = b.lo;
    last = std::max(last, s);
    before += b.count;
  }
  return bounds;
}

inline Int32
_sliceOf(ConstArrayView<Int64> bounds, Int64 uid)
{
  // Empty slices repeat a bound; the last of equal bounds is the one that holds uid.
  return static_cast<Int32>(std::upper_bound(bounds.begin(), bounds.end(), uid) - bounds.begin()) - 1;
}
 
} // namespace
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_computeFacesUniqueIdsParallelV1()
{
  if (m_is_v1_distributed) {
    _v1Distributed();
    return;
  }
 
  Integer nb_local_face = m_mesh_builder->oneMeshItemAdder()->nbFace();
 
  UniqueArray<Int64> faces_opposite_cell_uid(nb_local_face);
  faces_opposite_cell_uid.fill(NULL_ITEM_ID);
  UniqueArray<Integer> faces_opposite_cell_index(nb_local_face);
  UniqueArray<Integer> faces_opposite_cell_owner(nb_local_face);
  HashTableMapT<Int64, Int64> cells_first_face_uid(m_mesh_builder->oneMeshItemAdder()->nbCell() * 2, true);
  IntegerUniqueArray my_cells_nb_back_face;
  UniqueArray<T_CellFaceInfo> my_cells_faces_info;
 
  _v1ByAllGather(faces_opposite_cell_uid, faces_opposite_cell_index, faces_opposite_cell_owner,
                 cells_first_face_uid, my_cells_nb_back_face, my_cells_faces_info);
  _v1AssignFaceUniqueIds(faces_opposite_cell_uid, faces_opposite_cell_index, faces_opposite_cell_owner,
                         cells_first_face_uid, my_cells_nb_back_face);
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_v1Distributed()
{
  info() << "Computing FaceUniqueIds using distributed version 1";
  IParallelMng* pm = m_mesh->parallelMng();
  const Int32 nb_rank = pm->commSize();
  const Int32 my_rank = pm->commRank();
  ItemInternalMap& faces_map = m_mesh->facesMap();
  ItemInternalMap& cells_map = m_mesh->cellsMap();
  FaceLocalIdToFaceConverter faces(m_mesh->faceFamily());
  CellLocalIdToCellConverter cells_of(m_mesh->cellFamily());
  const Int32 nb_local_face = m_mesh_builder->oneMeshItemAdder()->nbFace();
 
  // The faces with one cell here, and the cells by increasing uniqueId.
  UniqueArray<Int32> bfaces;
  Int32 max_nb_node = 0;
  faces_map.eachItem([&](Face face) {
    if (face.isSubDomainBoundary()) {
      bfaces.add(face.localId());
      max_nb_node = std::max(max_nb_node, face.nbNode());
    }
  });
  const Int32 nb_bface = bfaces.size();
 
  UniqueArray<std::pair<Int64, Int32>> cells;
  cells.reserve(cells_map.count());
  Int32 has_foreign_cell = 0;
  cells_map.eachItem([&](Cell cell) {
    cells.add(std::make_pair(cell.uniqueId().asInt64(), cell.localId()));
    if (cell.owner() != my_rank)
      has_foreign_cell = 1;
  });
  std::sort(cells.begin(), cells.end());
  const Int32 nb_cell = cells.size();
 
  Int64 g_lo = 0;
  Int64 g_hi = 0;
  {
    Int64 v[4] = { max_nb_node, (nb_cell > 0) ? -cells[0].first : INT64_MIN,
                   (nb_cell > 0) ? cells[nb_cell - 1].first : INT64_MIN, has_foreign_cell };
    pm->reduce(Parallel::ReduceMax, ArrayView<Int64>(4, v));
    max_nb_node = CheckedConvert::toInt32(v[0]);
    has_foreign_cell = static_cast<Int32>(v[3]);
    if (v[2] == INT64_MIN)
      return; // no cell anywhere
    g_lo = -v[1];
    g_hi = v[2];
  }
 
  // --- Step 1, out: one record per face with one cell here, sorted node
  // uniqueIds padded with -1, then the uniqueId of the cell if it is in front
  // of the face, -1 if it is behind it.
  const Int32 s1 = max_nb_node + 1;
  UniqueArray<Int32> dest(nb_bface);
  UniqueArray<Int64> e1_count(nb_rank, 0);
  UniqueArray<Int64> keys(static_cast<Int64>(nb_bface) * max_nb_node);
  UniqueArray<Int64> nodes_uid;
  for (Int32 i = 0; i < nb_bface; ++i) {
    Face face(faces[bfaces[i]]);
    face.mutableItemBase().addFlags(ItemFlags::II_Shared | ItemFlags::II_SubDomainBoundary);
    nodes_uid.clear();
    for (Node node : face.nodes())
      nodes_uid.add(node.uniqueId().asInt64());
    std::sort(nodes_uid.begin(), nodes_uid.end());
    Int64* k = keys.data() + static_cast<Int64>(i) * max_nb_node;
    for (Int32 z = 0; z < max_nb_node; ++z)
      k[z] = (z < nodes_uid.size()) ? nodes_uid[z] : -1;
    dest[i] = _bucketOfHash(k[0], nb_rank);
    e1_count[dest[i]] += s1;
  }
  auto key_of = [&](Int32 i) { return keys.data() + static_cast<Int64>(i) * max_nb_node; };
  // The order of two node keys, uniqueId by uniqueId
  auto key_less = [max_nb_node](const Int64* ka, const Int64* kb) {
    for (Int32 z = 0; z < max_nb_node; ++z) {
      if (ka[z] != kb[z])
        return ka[z] < kb[z];
    }
    return false;
  };
  auto is_back = [&](Int32 i) { return (faces[bfaces[i]].itemBase().flags() & ItemFlags::II_HasBackCell) != 0; };
 
  UniqueArray<Int64> e1_index(nb_rank + 1, 0);
  for (Int32 r = 0; r < nb_rank; ++r)
    e1_index[r + 1] = e1_index[r] + e1_count[r] / s1;
  // sent[p] = the face sent at position p of the buffer
  UniqueArray<Int32> sent(nb_bface);
  UniqueArray<Int64> e1_send(static_cast<Int64>(nb_bface) * s1);
  {
    UniqueArray<Int64> at(e1_index.subConstView(0, nb_rank));
    for (Int32 i = 0; i < nb_bface; ++i) {
      const Int64 p = at[dest[i]]++;
      sent[CheckedConvert::toInt32(p)] = i;
      Int64* r = e1_send.data() + p * s1;
      const Int64* k = key_of(i);
      for (Int32 z = 0; z < max_nb_node; ++z)
        r[z] = k[z];
      r[max_nb_node] = is_back(i) ? -1 : faces[bfaces[i]].cell(0).uniqueId().asInt64();
    }
  }
  UniqueArray<Int64> e1_recv_count;
  const Int64 e1_round = Int64AllToAll::exchangeCounts(pm, e1_count, e1_recv_count);
  Int64AllToAll e1;
  e1.start(pm, e1_send, e1_count, e1_recv_count, e1_round);
 
  // --- While it travels: the runs, their slices, and step 2 out.
  UniqueArray<Int32> cell_nb_back(nb_cell, 0);
  UniqueArray<Int64> run_starts; // unsplit runs, for the slice bounds
  for (Int32 c = 0; c < nb_cell; ++c) {
    Cell cell(cells_of[cells[c].second]);
    Int32 n = 0;
    for (Face face : cell.faces()) {
      if (face.backCell() == cell)
        ++n;
    }
    cell_nb_back[c] = n;
    if (c == 0 || cells[c].first != cells[c - 1].first + 1)
      run_starts.add(cells[c].first);
  }
  const UniqueArray<Int64> bounds = _sliceBounds(pm, run_starts, g_lo, g_hi);
 
  // Runs cut at the slice bounds: [run_first[r], run_first[r] + run_count[r]) are
  // cells[run_cell[r] ...], all in slice run_slice[r].
  UniqueArray<Int32> run_cell;
  UniqueArray<Int32> run_slice;
  UniqueArray<Int64> slice_total(nb_rank, 0); // this rank's part of every slice's total
  {
    Int32 s = 0;
    for (Int32 c = 0; c < nb_cell; ++c) {
      const Int64 uid = cells[c].first;
      const Int32 old_s = s;
      while (uid >= bounds[s + 1])
        ++s;
      if (c == 0 || uid != cells[c - 1].first + 1 || s != old_s) {
        run_cell.add(c);
        run_slice.add(s);
      }
      slice_total[s] += cell_nb_back[c];
    }
  }
  const Int32 nb_run = run_cell.size();
  run_cell.add(nb_cell);
  UniqueArray<Int64> e2_count(nb_rank, 0);
  for (Int32 r = 0; r < nb_run; ++r)
    e2_count[run_slice[r]] += 3;
  UniqueArray<Int64> e2_index(nb_rank + 1, 0);
  for (Int32 r = 0; r < nb_rank; ++r)
    e2_index[r + 1] = e2_index[r] + e2_count[r] / 3;
  UniqueArray<Int32> run_sent(nb_run); // run_sent[p] = the run sent at position p
  UniqueArray<Int64> e2_send(static_cast<Int64>(nb_run) * 3);
  {
    UniqueArray<Int64> at(e2_index.subConstView(0, nb_rank));
    for (Int32 r = 0; r < nb_run; ++r) {
      const Int64 p = at[run_slice[r]]++;
      run_sent[CheckedConvert::toInt32(p)] = r;
      Int64 nb_back = 0;
      for (Int32 c = run_cell[r]; c < run_cell[r + 1]; ++c)
        nb_back += cell_nb_back[c];
      e2_send[p * 3 + 0] = cells[run_cell[r]].first;
      e2_send[p * 3 + 1] = run_cell[r + 1] - run_cell[r];
      e2_send[p * 3 + 2] = nb_back;
    }
  }
  UniqueArray<Int64> e2_recv_count;
  const Int64 e2_round = Int64AllToAll::exchangeCounts(pm, e2_count, e2_recv_count);
  Int64AllToAll e2;
  e2.start(pm, e2_send, e2_count, e2_recv_count, e2_round);
 
  // --- Step 1 at the meeting rank: pair the halves.
  e1.wait();
  const Int32 n1 = CheckedConvert::toInt32(e1.received().size() / s1);
  UniqueArray<Int32> rec_src(n1);
  UniqueArray<Int32> rec_pos(n1);
  for (Int32 r = 0, i = 0; r < nb_rank; ++r) {
    const Int32 n = CheckedConvert::toInt32(e1_recv_count[r] / s1);
    for (Int32 p = 0; p < n; ++p, ++i) {
      rec_src[i] = r;
      rec_pos[i] = p;
    }
  }
  auto rec_of = [&](Int32 i) { return e1.received().data() + static_cast<Int64>(i) * s1; };
  UniqueArray<Int32> order(n1);
  for (Int32 i = 0; i < n1; ++i)
    order[i] = i;
  std::sort(order.begin(), order.end(), [&](Int32 a, Int32 b) { return key_less(rec_of(a), rec_of(b)); });
  auto same_key = [&](Int32 a, Int32 b) {
    const Int64* ka = rec_of(a);
    const Int64* kb = rec_of(b);
    for (Int32 z = 0; z < max_nb_node; ++z) {
      if (ka[z] != kb[z])
        return false;
    }
    return true;
  };
  auto key_string = [&](Int32 a) {
    OStringStream o;
    for (Int32 z = 0; z < max_nb_node && rec_of(a)[z] >= 0; ++z)
      o() << ' ' << rec_of(a)[z];
    return o.str();
  };
 
  // Answers to the halves of a pair, (position << 32) | rank of the other half;
  // the cells in front of a lone face, to the rank of their slice.
  UniqueArray<Int64> pair_answer; // (destination, answer) flattened
  UniqueArray<Int64> lone_cell;   // (slice, cell uid) flattened
  for (Int32 i = 0; i < n1;) {
    Int32 j = i + 1;
    while (j < n1 && same_key(order[i], order[j]))
      ++j;
    const Int32 a = order[i];
    if (j - i == 1) {
      const Int64 cell_uid = rec_of(a)[max_nb_node];
      if (cell_uid >= 0) {
        const Int32 s = _sliceOf(bounds, cell_uid);
        lone_cell.add(s);
        lone_cell.add(cell_uid);
        slice_total[s] += 1;
      }
    }
    else if (j - i == 2) {
      const Int32 b = order[i + 1];
      if (rec_src[a] == rec_src[b])
        ARCANE_FATAL("Face numbering: the face of nodes ({0}) is held twice by sub-domain {1}",
                     key_string(a), rec_src[a]);
      if ((rec_of(a)[max_nb_node] < 0) == (rec_of(b)[max_nb_node] < 0))
        ARCANE_FATAL("Face numbering: the face of nodes ({0}) is {1} in sub-domains {2} and {3}",
                     key_string(a), (rec_of(a)[max_nb_node] < 0) ? "behind its cell" : "in front of its cell",
                     rec_src[a], rec_src[b]);
      pair_answer.add(rec_src[a]);
      pair_answer.add((static_cast<Int64>(rec_pos[a]) << 32) | rec_src[b]);
      pair_answer.add(rec_src[b]);
      pair_answer.add((static_cast<Int64>(rec_pos[b]) << 32) | rec_src[a]);
    }
    else
      ARCANE_FATAL("Face numbering: the face of nodes ({0}) is held by {1} sub-domains",
                   key_string(a), j - i);
    i = j;
  }
 
  // The totals of the slices, summed while step 1 comes back.
  UniqueArray<Int64> g_slice_total(nb_rank, 0);
  Parallel::Request total_request;
  IParallelNonBlockingCollective* nbc = pm->nonBlockingCollective();
  if (nbc)
    total_request = nbc->allReduce(Parallel::ReduceSum, slice_total, g_slice_total);
  else {
    g_slice_total.copy(slice_total);
    pm->reduce(Parallel::ReduceSum, g_slice_total);
  }
 
  // --- Step 1, back: to each rank [nb answers][answers][lone cells].
  UniqueArray<Int64> b_count(nb_rank, 1);
  UniqueArray<Int64> b_nb_answer(nb_rank, 0);
  for (Int64 k = 0; k < pair_answer.size(); k += 2) {
    ++b_count[pair_answer[k]];
    ++b_nb_answer[pair_answer[k]];
  }
  for (Int64 k = 0; k < lone_cell.size(); k += 2)
    ++b_count[lone_cell[k]];
  UniqueArray<Int64> b_index(nb_rank + 1, 0);
  for (Int32 r = 0; r < nb_rank; ++r)
    b_index[r + 1] = b_index[r] + b_count[r];
  UniqueArray<Int64> b_send(b_index[nb_rank]);
  {
    UniqueArray<Int64> at(nb_rank);
    for (Int32 r = 0; r < nb_rank; ++r) {
      b_send[b_index[r]] = b_nb_answer[r];
      at[r] = b_index[r] + 1;
    }
    for (Int64 k = 0; k < pair_answer.size(); k += 2)
      b_send[at[pair_answer[k]]++] = pair_answer[k + 1];
    for (Int64 k = 0; k < lone_cell.size(); k += 2)
      b_send[at[lone_cell[k]]++] = lone_cell[k + 1];
  }
  UniqueArray<Int64> b_recv_count;
  const Int64 b_round = Int64AllToAll::exchangeCounts(pm, b_count, b_recv_count);
  Int64AllToAll e1b;
  e1b.start(pm, b_send, b_count, b_recv_count, b_round);
  e1b.wait();
 
  // partner[i] = the rank holding the other half of face i, -1 if it is alone.
  UniqueArray<Int32> partner(nb_bface, -1);
  UniqueArray<Int64> my_lone; // cells of my slice in front of a lone face
  for (Int32 r = 0; r < nb_rank; ++r) {
    Span<const Int64> m = e1b.from(r);
    const Int64 nb_answer = m[0];
    for (Int64 k = 1; k <= nb_answer; ++k) {
      const Int64 pos = m[k] >> 32;
      const Int32 other = static_cast<Int32>(m[k] & 0xffffffff);
      partner[sent[CheckedConvert::toInt32(e1_index[r] + pos)]] = other;
    }
    for (Int64 k = nb_answer + 1; k < m.size(); ++k)
      my_lone.add(m[k]);
  }
  std::sort(my_lone.begin(), my_lone.end());
 
  // --- Step 2 at the rank of the slice: the runs in order, the lone faces
  // in their cells, and the start of every run.
  e2.wait();
  if (nbc)
    pm->waitAllRequests(ArrayView<Parallel::Request>(1, &total_request));
  Int64 slice_start = 0;
  for (Int32 r = 0; r < my_rank; ++r)
    slice_start += g_slice_total[r];
  const Int32 n2 = CheckedConvert::toInt32(e2.received().size() / 3);
  const Int64* runs = e2.received().data();
  UniqueArray<Int32> run_order(n2);
  for (Int32 i = 0; i < n2; ++i)
    run_order[i] = i;
  std::sort(run_order.begin(), run_order.end(),
            [&](Int32 a, Int32 b) { return runs[a * 3] < runs[b * 3]; });
  UniqueArray<Int64> a_send(n2);
  {
    Int64 running = slice_start;
    Int64 end_prev = INT64_MIN;
    Int32 l = 0;
    const Int32 nb_lone = my_lone.size();
    for (Int32 i = 0; i < n2; ++i) {
      const Int64* run = runs + run_order[i] * 3;
      const Int64 first = run[0];
      const Int64 end = first + run[1];
      if (first < end_prev)
        ARCANE_FATAL("Face numbering: the cell uniqueId={0} is held by two sub-domains", first);
      if (l < nb_lone && my_lone[l] < first)
        ARCANE_FATAL("Face numbering: the cell uniqueId={0} of a boundary face is held by no sub-domain", my_lone[l]);
      a_send[run_order[i]] = running;
      running += run[2];
      for (; l < nb_lone && my_lone[l] < end; ++l)
        ++running;
      end_prev = end;
    }
    if (l < nb_lone)
      ARCANE_FATAL("Face numbering: the cell uniqueId={0} of a boundary face is held by no sub-domain", my_lone[l]);
    if (running - slice_start != g_slice_total[my_rank])
      ARCANE_FATAL("Face numbering: slice {0} counts {1} faces, its runs {2}",
                   my_rank, g_slice_total[my_rank], running - slice_start);
  }
 
  // --- Step 2, back: one start per run, in the order the runs came.
  UniqueArray<Int64> a_count(nb_rank);
  UniqueArray<Int64> a_recv_count(nb_rank);
  for (Int32 r = 0; r < nb_rank; ++r) {
    a_count[r] = e2_recv_count[r] / 3;
    a_recv_count[r] = e2_count[r] / 3;
  }
  Int64AllToAll e2b;
  e2b.start(pm, a_send, a_count, a_recv_count, e2_round);
  e2b.wait();
 
  // --- Every face of a cell of this rank that it numbers.
  UniqueArray<Int64> faces_new_uid(nb_local_face);
  faces_new_uid.fill(NULL_ITEM_ID);
  UniqueArray<Int8> is_lone(nb_local_face, 0);
  for (Int32 i = 0; i < nb_bface; ++i) {
    if (partner[i] < 0)
      is_lone[bfaces[i]] = 1;
  }
  for (Int32 p = 0; p < nb_run; ++p) {
    const Int32 r = run_sent[p];
    Int64 start = e2b.received()[p];
    for (Int32 c = run_cell[r]; c < run_cell[r + 1]; ++c) {
      Cell cell(cells_of[cells[c].second]);
      Integer num_back = 0;
      Integer num_lone = 0;
      for (Face face : cell.faces()) {
        Int64 face_new_uid = NULL_ITEM_UNIQUE_ID;
        if (face.backCell() == cell) {
          face_new_uid = start + num_back;
          ++num_back;
        }
        else if (face.nbCell() == 1 && is_lone[face.localId()]) {
          face_new_uid = start + cell_nb_back[c] + num_lone;
          ++num_lone;
        }
        if (face_new_uid != NULL_ITEM_UNIQUE_ID) {
          faces_new_uid[face.localId()] = face_new_uid;
          face.mutableItemBase().setUniqueId(face_new_uid);
          face.mutableItemBase().setOwner(my_rank, my_rank);
        }
      }
      start += cell_nb_back[c] + num_lone;
    }
  }
 
  // --- Step 3: the rank behind a shared face tells the rank in front.
  {
    const Int32 s3 = has_foreign_cell ? 2 : 1;
    // The shared faces grouped by partner, back ones and front ones apart,
    // each group in node order: both sides list the faces they share alike.
    UniqueArray<Int32> shared;
    for (Int32 i = 0; i < nb_bface; ++i) {
      if (partner[i] >= 0)
        shared.add(i);
    }
    std::sort(shared.begin(), shared.end(), [&](Int32 a, Int32 b) {
      if (partner[a] != partner[b])
        return partner[a] < partner[b];
      return key_less(key_of(a), key_of(b));
    });
    // The messages of step 3 are no larger than those of step 1, so they
    // need no more rounds; their sizes are known on both sides.
    UniqueArray<Int64> e3_count(nb_rank, 0);
    UniqueArray<Int64> e3_recv_count(nb_rank, 0);
    UniqueArray<UniqueArray<Int32>> in_face(nb_rank);
    for (Int32 i : shared) {
      if (is_back(i))
        e3_count[partner[i]] += s3;
      else {
        in_face[partner[i]].add(i);
        e3_recv_count[partner[i]] += s3;
      }
    }
    UniqueArray<Int64> e3_send;
    for (Int32 i : shared) {
      if (is_back(i)) {
        e3_send.add(faces_new_uid[bfaces[i]]);
        if (s3 == 2)
          e3_send.add(faces[bfaces[i]].cell(0).owner());
      }
    }
    Int64AllToAll e3;
    e3.start(pm, e3_send, e3_count, e3_recv_count, e1_round);
    e3.wait();
    for (Int32 p = 0; p < nb_rank; ++p) {
      Span<const Int64> in = e3.from(p);
      for (Int32 k = 0; k < in_face[p].size(); ++k) {
        Face face(faces[bfaces[in_face[p][k]]]);
        const Int64 uid = in[static_cast<Int64>(k) * s3];
        const Int32 owner = (s3 == 2) ? static_cast<Int32>(in[static_cast<Int64>(k) * s3 + 1]) : p;
        faces_new_uid[face.localId()] = uid;
        face.mutableItemBase().setUniqueId(uid);
        face.mutableItemBase().setOwner(owner, my_rank);
      }
    }
  }
 
  // Only the verbose listing reads it; the cell on the other side of a shared
  // face is not known here.
  UniqueArray<Int64> faces_opposite_cell_uid;
  if (m_mesh_builder->isVerbose()) {
    faces_opposite_cell_uid.resize(nb_local_face, NULL_ITEM_ID);
    for (Int32 i = 0; i < nb_bface; ++i) {
      if (partner[i] >= 0)
        faces_opposite_cell_uid[bfaces[i]] = -2;
    }
  }
  _v1CheckAndDump(faces_new_uid, faces_opposite_cell_uid);
 
  info() << "Distributed face numbering: " << nb_bface << " faces with one cell, "
         << nb_run << " runs of cells, " << n2 << " runs in slice " << my_rank;
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_v1CellBlockSizes(Int64ConstArrayView faces_opposite_cell_uid,
                  IntegerArray& my_cells_nb_back_face,
                  Array<T_CellFaceInfo>& my_cells_faces_info)
{
  ItemInternalMap& cells_map = m_mesh->cellsMap();
  Int32 max_cell_local_id = 0;
  cells_map.eachItem([&](Item cell) {
    max_cell_local_id = std::max(max_cell_local_id, cell.localId());
  });
  my_cells_nb_back_face.resize(max_cell_local_id + 1);
  my_cells_nb_back_face.fill(0);
  my_cells_faces_info.clear();
  my_cells_faces_info.reserve(m_mesh_builder->oneMeshItemAdder()->nbCell());
 
  cells_map.eachItem([&](Cell cell) {
    Int64 cell_uid = cell.uniqueId().asInt64();
    Int32 cell_local_id = cell.localId();
    Integer nb_back_face = 0;
    Integer nb_true_boundary_face = 0;
    for (Face face : cell.faces()) {
      Int64 opposite_cell_uid = faces_opposite_cell_uid[face.localId()];
      if (face.backCell() == cell)
        ++nb_back_face;
      else if (face.nbCell() == 1 && opposite_cell_uid == NULL_ITEM_ID) {
        ++nb_true_boundary_face;
      }
    }
    my_cells_nb_back_face[cell_local_id] = nb_back_face;
    my_cells_faces_info.add(T_CellFaceInfo(cell_uid, nb_back_face, nb_true_boundary_face));
  });
  std::sort(std::begin(my_cells_faces_info), std::end(my_cells_faces_info));
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_v1CheckAndDump(Int64ConstArrayView faces_new_uid, Int64ConstArrayView faces_opposite_cell_uid)
{
  Integer my_rank = m_mesh->parallelMng()->commRank();
  Integer nb_local_face = m_mesh_builder->oneMeshItemAdder()->nbFace();
  bool is_verbose = m_mesh_builder->isVerbose();
  ItemInternalMap& cells_map = m_mesh->cellsMap();
 
  // Verifies that all faces have been re-indexed
  {
    Integer nb_error = 0;
    for (Integer i = 0, is = nb_local_face; i < is; ++i) {
      if (faces_new_uid[i] == NULL_ITEM_UNIQUE_ID) {
        ++nb_error;
        if (nb_error < 10)
          error() << "The face lid=" << i << " has not been re-indexed.";
      }
    }
    if (nb_error != 0)
      ARCANE_FATAL("Some ({0}) faces have not been reindexed", nb_error);
  }
 
  if (is_verbose) {
    OStringStream ostr;
    cells_map.eachItem([&](Cell cell) {
      Int64 cell_uid = cell.uniqueId().asInt64();
      Integer face_index = 0;
      for (Face face : cell.faces()) {
        Int64 opposite_cell_uid = faces_opposite_cell_uid[face.localId()];
        bool shared = false;
        bool true_boundary = false;
        bool internal_other = false;
        if (face.backCell() == cell) {
        }
        else if (face.nbCell() == 1) {
          if (opposite_cell_uid == NULL_ITEM_ID)
            true_boundary = true;
          else
            shared = true;
        }
        else {
          internal_other = true;
          opposite_cell_uid = face.backCell().uniqueId().asInt64();
        }
        ostr() << "NEW UNIQUE ID FOR FACE"
               << " lid=" << face.localId()
               << " cell=" << cell_uid
               << " face=" << face.uniqueId()
               << " nbcell=" << face.nbCell()
               << " cellindex=" << face_index << " (";
        for (Node node : face.nodes())
          ostr() << ' ' << node.uniqueId();
        ostr() << ")";
        if (internal_other)
          ostr() << " internal-other";
        if (true_boundary)
          ostr() << " true-boundary";
        if (opposite_cell_uid >= 0) {
          ostr() << " opposite " << opposite_cell_uid;
        }
        if (shared)
          ostr() << " (shared)";
        ostr() << "\n";
        ++face_index;
      }
    });
    info() << ostr.str();
    String file_name("faces_uid.");
    file_name = file_name + my_rank;
    std::ofstream ofile(file_name.localstr());
    ofile << ostr.str();
  }
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_v1AssignFaceUniqueIds(Int64ConstArrayView faces_opposite_cell_uid,
                       IntegerConstArrayView faces_opposite_cell_index,
                       IntegerConstArrayView faces_opposite_cell_owner,
                       HashTableMapT<Int64, Int64>& cells_first_face_uid,
                       IntegerConstArrayView my_cells_nb_back_face)
{
  IParallelMng* pm = m_mesh->parallelMng();
  Integer my_rank = pm->commRank();
  Integer nb_local_face = m_mesh_builder->oneMeshItemAdder()->nbFace();
  ItemInternalMap& cells_map = m_mesh->cellsMap();
 
  // For verification, ensures that all elements of this array
  // are valid, which means that all faces have been
  // renumbered
  UniqueArray<Int64> faces_new_uid(nb_local_face);
  faces_new_uid.fill(NULL_ITEM_ID);
 
  cells_map.eachItem([&](Cell cell) {
    Int64 cell_uid = cell.uniqueId();
    Int32 cell_local_id = cell.localId();
    Integer num_local_face = 0;
    Integer num_true_boundary_face = 0;
    for (Face face : cell.faces()) {
      Int64 opposite_cell_uid = faces_opposite_cell_uid[face.localId()];
      Int64 face_new_uid = NULL_ITEM_UNIQUE_ID;
      if (face.backCell() == cell) {
        if (!cells_first_face_uid.hasKey(cell_uid))
          fatal() << "NO KEY 0 for cell_uid=" << cell_uid;
        face_new_uid = cells_first_face_uid[cell_uid] + num_local_face;
        face.mutableItemBase().setOwner(my_rank, my_rank);
        ++num_local_face;
      }
      else if (face.nbCell() == 1) {
        if (opposite_cell_uid == NULL_ITEM_UNIQUE_ID) {
          // This is a boundary face of the initial domain
          if (!cells_first_face_uid.hasKey(cell_uid))
            fatal() << "NO KEY 1 for cell_uid=" << cell_uid;
          face_new_uid = cells_first_face_uid[cell_uid] + my_cells_nb_back_face[cell_local_id] + num_true_boundary_face;
          ++num_true_boundary_face;
          face.mutableItemBase().setOwner(my_rank, my_rank);
        }
        else {
          if (!cells_first_face_uid.hasKey(opposite_cell_uid))
            fatal() << "NO KEY 1 for cell_uid=" << cell_uid << " opoosite=" << opposite_cell_uid;
          face_new_uid = cells_first_face_uid[opposite_cell_uid] + faces_opposite_cell_index[face.localId()];
          face.mutableItemBase().setOwner(faces_opposite_cell_owner[face.localId()], my_rank);
        }
      }
      if (face_new_uid != NULL_ITEM_UNIQUE_ID) {
        faces_new_uid[face.localId()] = face_new_uid;
        face.mutableItemBase().setUniqueId(face_new_uid);
      }
    }
  });
 
  _v1CheckAndDump(faces_new_uid, faces_opposite_cell_uid);
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_v1ByAllGather(Int64ArrayView faces_opposite_cell_uid,
               IntegerArrayView faces_opposite_cell_index,
               IntegerArrayView faces_opposite_cell_owner,
               HashTableMapT<Int64, Int64>& cells_first_face_uid,
               IntegerArray& my_cells_nb_back_face,
               Array<T_CellFaceInfo>& my_cells_faces_info)
{
  IParallelMng* pm = m_mesh->parallelMng();
  Integer my_rank = pm->commRank();
  Integer nb_rank = pm->commSize();
 
  Integer nb_local_face = m_mesh_builder->oneMeshItemAdder()->nbFace();
 
  Integer nb_recv_sub_domain_boundary_face = 0;
 
  Int64UniqueArray faces_infos;
  faces_infos.reserve(10000);
  ItemInternalMap& cells_map = m_mesh->cellsMap();
  ItemInternalMap& faces_map = m_mesh->facesMap();
  ItemInternalMap& nodes_map = m_mesh->nodesMap();
 
  // Gather data from other processors into recv_cells;
  // To prevent the arrays from being too large, we proceed in several
  // steps.
  // Each sub-domain builds its list of boundary faces, with for each face:
  // - its type
  // - the list of its nodes,
  // - the unique number of its cell
  // - the owner of its cell
  // - its index in its cell
  // This list will then be sent to all sub-domains.
  {
    ItemTypeMng* itm = m_mesh->itemTypeMng();
 
    UniqueArray<Int32> faces_local_id;
 
    faces_map.eachItem([&](Face face) {
      bool boundary_val = face.isSubDomainBoundary();
      if (boundary_val)
        faces_local_id.add(face.localId());
    });
 
    Integer nb_sub_domain_boundary_face = faces_local_id.size();
    Int64 global_nb_boundary_face = pm->reduce(Parallel::ReduceSum, (Int64)nb_sub_domain_boundary_face);
    debug() << "NB BOUNDARY FACE=" << nb_sub_domain_boundary_face
            << " NB_FACE=" << nb_local_face
            << " GLOBAL_NB_BOUNDARY_FACE=" << global_nb_boundary_face;
 
    Int64UniqueArray faces_infos2;
    Int64UniqueArray recv_faces_infos;
 
    // Calculate the size of a send block
    // The memory required for a face is equal to nb_node + 4.
    // If we assume we have quadrangles in general, this
    // makes 8 Int64 per face, or 64 bytes per face.
    // The memory required to send everything is therefore 64 * global_nb_boundary_face.
    // step_size * nb_proc * 64 bytes.
    // The default step_size is calculated so that the required memory
    // is on the order of 100 Mo for each message.
    Int64 step_size = 1500000;
    Integer nb_phase = CheckedConvert::toInteger((global_nb_boundary_face / step_size) + 1);
    FaceLocalIdToFaceConverter faces(m_mesh->faceFamily());
    for (Integer i_phase = 0; i_phase < nb_phase; ++i_phase) {
      Integer nb_face_to_send = nb_sub_domain_boundary_face / nb_phase;
      Integer first_face_to_send = nb_face_to_send * i_phase;
      Integer last_face_to_send = first_face_to_send + nb_face_to_send;
      if (i_phase + 1 == nb_phase)
        last_face_to_send = nb_sub_domain_boundary_face;
      Integer real_nb_face_to_send = last_face_to_send - first_face_to_send;
 
      faces_infos2.clear();
      for (Integer i_face = first_face_to_send; i_face < first_face_to_send + real_nb_face_to_send; ++i_face) {
        Face face(faces[faces_local_id[i_face]]);
        face.mutableItemBase().addFlags(ItemFlags::II_Shared | ItemFlags::II_SubDomainBoundary);
        bool has_back_cell = face.itemBase().flags() & ItemFlags::II_HasBackCell;
        faces_infos2.add(face.type());
        for (Node node : face.nodes())
          faces_infos2.add(node.uniqueId().asInt64());
 
        //info() << " ADD FACE lid=" << face->localId();
 
        Cell cell = face.cell(0);
        faces_infos2.add(cell.uniqueId().asInt64());
        faces_infos2.add(cell.owner());
 
        Integer face_index_in_cell = 0;
        if (has_back_cell) {
          for (Face current_face_in_cell : cell.faces()) {
            if (current_face_in_cell == face)
              break;
            if (current_face_in_cell.backCell() == cell)
              ++face_index_in_cell;
          }
        }
        else
          face_index_in_cell = NULL_ITEM_ID;
        faces_infos2.add(face_index_in_cell);
      }
      faces_infos2.add(IT_NullType); // To indicate that the list ends
 
      pm->allGatherVariable(faces_infos2, recv_faces_infos);
 
      info() << "Number of face bytes received: " << recv_faces_infos.size()
             << " phase=" << i_phase << "/" << nb_phase
             << " first_face=" << first_face_to_send
             << " last_face=" << last_face_to_send
             << " nb=" << real_nb_face_to_send;
 
      Integer recv_faces_infos_index = 0;
 
      for (Integer i_sub_domain = 0; i_sub_domain < nb_rank; ++i_sub_domain) {
        bool is_end = false;
        // We must not read the info that comes from me
        if (i_sub_domain == my_rank) {
          recv_faces_infos_index += faces_infos2.size();
          continue;
        }
        // Deserializes the info for each subdomain
        while (!is_end) {
          Integer face_type = CheckedConvert::toInteger(recv_faces_infos[recv_faces_infos_index]);
          ++recv_faces_infos_index;
          if (face_type == IT_NullType) {
            is_end = true;
            break;
          }
          ItemTypeInfo* itt = itm->typeFromId(face_type);
          Integer face_nb_node = itt->nbLocalNode();
          ConstArrayView<Int64> faces_nodes_uid(face_nb_node, &recv_faces_infos[recv_faces_infos_index]);
 
          recv_faces_infos_index += face_nb_node;
          Int64 cell_uid = recv_faces_infos[recv_faces_infos_index];
          ++recv_faces_infos_index;
          Integer cell_owner = CheckedConvert::toInteger(recv_faces_infos[recv_faces_infos_index]);
          ++recv_faces_infos_index;
          Integer cell_face_index = CheckedConvert::toInteger(recv_faces_infos[recv_faces_infos_index]);
          ++recv_faces_infos_index;
 
          Node node = nodes_map.tryFind(faces_nodes_uid[0]);
          // If the face does not exist in my subdomain, it is not of interest to me
          if (node.null())
            continue;
          Face face = ItemTools::findFaceInNode2(node, face_type, faces_nodes_uid);
          if (face.null())
            continue;
          ++nb_recv_sub_domain_boundary_face;
          faces_opposite_cell_uid[face.localId()] = cell_uid;
          faces_opposite_cell_index[face.localId()] = cell_face_index;
          faces_opposite_cell_owner[face.localId()] = cell_owner;
          cells_first_face_uid.add(cell_uid, -1);
        }
      }
    }
    info() << "Number of faces on the subdomain interface: "
           << nb_sub_domain_boundary_face << ' ' << nb_recv_sub_domain_boundary_face;
  }
 
  // Finds the max uniqueId of the cells across all subdomains.
  Int64 max_cell_uid = 0;
  cells_map.eachItem([&](Item cell) {
    Int64 cell_uid = cell.uniqueId().asInt64();
    if (cell_uid > max_cell_uid)
      max_cell_uid = cell_uid;
  });
  Int64 global_max_cell_uid = pm->reduce(Parallel::ReduceMax, max_cell_uid);
  debug() << "GLOBAL MAX CELL UID=" << global_max_cell_uid;
 
  _v1CellBlockSizes(faces_opposite_cell_uid, my_cells_nb_back_face, my_cells_faces_info);
 
  {
    Integer nb_phase = 16;
    Integer first_cell_index_to_send = 0;
    Int64 current_face_uid = 0;
 
    for (Integer i_phase = 0; i_phase < nb_phase; ++i_phase) {
      Integer nb_uid_to_send = CheckedConvert::toInteger(global_max_cell_uid / nb_phase);
      Integer first_uid_to_send = nb_uid_to_send * i_phase;
      Int64 last_uid_to_send = first_uid_to_send + nb_uid_to_send;
      if (i_phase + 1 == nb_phase)
        last_uid_to_send = global_max_cell_uid;
 
      //Integer last_cell_index_to_send = first_cell_index_to_send;
      Integer nb_cell_to_send = 0;
      for (Integer zz = first_cell_index_to_send, zs = my_cells_faces_info.size(); zz < zs; ++zz) {
        if (my_cells_faces_info[zz].m_unique_id <= last_uid_to_send)
          ++nb_cell_to_send;
        else
          break;
      }
      debug() << "FIRST TO SEND=" << first_cell_index_to_send
              << " NB=" << nb_cell_to_send
              << " first_uid=" << first_uid_to_send
              << " last_uid=" << last_uid_to_send;
 
      T_CellFaceInfo* begin_cell_array = my_cells_faces_info.data() + first_cell_index_to_send;
      Int64* begin_array = reinterpret_cast<Int64*>(begin_cell_array);
      Integer begin_size = nb_cell_to_send * 3;
 
      Int64ConstArrayView cells_faces_infos(begin_size, begin_array);
 
      Int64UniqueArray recv_cells_faces_infos;
      pm->allGatherVariable(cells_faces_infos, recv_cells_faces_infos);
      first_cell_index_to_send += nb_cell_to_send;
 
      info() << "Infos faces (received) nb_int64=" << recv_cells_faces_infos.size();
      Integer recv_nb_cell = recv_cells_faces_infos.size() / 3;
 
      // NOTE: since we know the possible min and max uid, we can optimize by
      // creating an array dimensioned with this min and max as bounds and
      // filling the elements of this array directly. This way, we
      UniqueArray<T_CellFaceInfo> global_cells_faces_info(recv_nb_cell);
      for (Integer i = 0; i < recv_nb_cell; ++i) {
        Int64 cell_uid = recv_cells_faces_infos[i * 3];
        global_cells_faces_info[i].m_unique_id = cell_uid;
        global_cells_faces_info[i].m_nb_back_face = recv_cells_faces_infos[(i * 3) + 1];
        global_cells_faces_info[i].m_nb_true_boundary_face = recv_cells_faces_infos[(i * 3) + 2];
      }
      info() << "Sorting the faces nb=" << global_cells_faces_info.size();
      std::sort(std::begin(global_cells_faces_info), std::end(global_cells_faces_info));
 
      for (Integer i = 0; i < recv_nb_cell; ++i) {
        Int64 cell_uid = global_cells_faces_info[i].m_unique_id;
        if (cells_map.hasKey(cell_uid) || cells_first_face_uid.hasKey(cell_uid))
          cells_first_face_uid.add(cell_uid, current_face_uid);
        current_face_uid += global_cells_faces_info[i].m_nb_back_face + global_cells_faces_info[i].m_nb_true_boundary_face;
      }
    }
  }
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_exchangeData(IParallelExchanger* exchanger, BoundaryInfosMap& boundary_infos_to_send)
{
  for (BoundaryInfosMapEnumerator i_map(boundary_infos_to_send); ++i_map;) {
    Int32 sd = i_map.data()->key();
    exchanger->addSender(sd);
  }
  exchanger->initializeCommunicationsMessages();
  Integer nb_sender = exchanger->nbSender();
  Integer nb_receiver = exchanger->nbReceiver();
  info() << "NB_SEND=" << nb_sender << " NB_RECV=" << nb_receiver;
  Integer total = nb_sender + nb_receiver;
  Integer global_total = exchanger->parallelMng()->reduce(Parallel::ReduceSum, total);
  info() << "GLOBAL_NB_MESSAGE=" << global_total;
 
  {
    for (Integer i = 0, ns = exchanger->nbSender(); i < ns; ++i) {
      ISerializeMessage* sm = exchanger->messageToSend(i);
      Int32 rank = sm->destination().value();
      ISerializer* s = sm->serializer();
      Int64ConstArrayView infos = boundary_infos_to_send[rank];
      Integer nb_info = infos.size();
      s->setMode(ISerializer::ModeReserve);
      s->reserveInt64(1); // For the number of elements
      s->reserveSpan(eBasicDataType::Int64, nb_info); // For the elements
      s->allocateBuffer();
      s->setMode(ISerializer::ModePut);
      s->putInt64(nb_info);
      s->putSpan(infos);
    }
  }
  exchanger->processExchange();
  debug() << "END EXCHANGE";
}
 
template <typename DataType>
class ItemInfoMultiList
{
 public:
 private:
 
  class MyInfo
  {
   public:
 
    MyInfo(const DataType& d, Integer n)
    : data(d)
    , next_index(n)
    {}
 
   public:
 
    DataType data;
    Integer next_index;
  };
 
 public:
 
  ItemInfoMultiList()
  : m_last_index(5000, true)
  {}
 
 public:
 
  void add(Int64 node_uid, const DataType& data)
  {
    Integer current_index = m_values.size();
 
    bool is_add = false;
    HashTableMapT<Int64, Int32>::Data* d = m_last_index.lookupAdd(node_uid, -1, is_add);
 
    m_values.add(MyInfo(data, d->value()));
    d->value() = current_index;
  }
 
 public:
 
  UniqueArray<MyInfo> m_values;
  HashTableMapT<Int64, Int32> m_last_index;
};
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_computeFacesUniqueIdsParallelV2()
{
  IParallelMng* pm = m_mesh->parallelMng();
  Integer my_rank = pm->commRank();
  Integer nb_rank = pm->commSize();
 
  Integer nb_local_face = m_mesh_builder->oneMeshItemAdder()->nbFace();
  //Integer nb_local_cell = m_mesh_builder->nbCell();
  //bool is_verbose = m_mesh_builder->isVerbose();
 
  Int64UniqueArray faces_opposite_cell_uid(nb_local_face);
  faces_opposite_cell_uid.fill(NULL_ITEM_ID);
  IntegerUniqueArray faces_opposite_cell_index(nb_local_face);
  IntegerUniqueArray faces_opposite_cell_owner(nb_local_face);
 
  // For verification, ensures that all elements of this array
  // are valid, which means that all faces have been renumbered.
  Int64UniqueArray faces_new_uid(nb_local_face);
  faces_new_uid.fill(NULL_ITEM_ID);
 
  Int64UniqueArray faces_infos;
  faces_infos.reserve(10000);
  ItemInternalMap& faces_map = m_mesh->facesMap();
  ItemInternalMap& nodes_map = m_mesh->nodesMap();
 
  // NOTE: this array is not useful on all cells. It
  // is enough that it contains the cells we need, that is,
  // ours + those connected to one of our faces.
  HashTableMapT<Int32, Int32> cell_first_face_uid(m_mesh_builder->oneMeshItemAdder()->nbCell() * 2, true);
 
  // Collects data from other processors into recv_cells;
  // To prevent the arrays from being too large, we proceed in several
  // steps.
  // Each subdomain builds its list of boundary faces, for each face:
  // - its type
  // - the list of its nodes,
  // - the unique ID of its cell
  // - the owner of its cell
  // - its index in its cell
  // This list will then be sent to all subdomains.
  ItemTypeMng* itm = m_mesh->itemTypeMng();
 
  // Determines the max unique id of the nodes
  Int64 my_max_node_uid = NULL_ITEM_UNIQUE_ID;
  nodes_map.eachItem([&](Item node) {
    Int64 node_uid = node.uniqueId();
    if (node_uid > my_max_node_uid)
      my_max_node_uid = node_uid;
  });
  Int64 global_max_node_uid = pm->reduce(Parallel::ReduceMax, my_max_node_uid);
  debug() << "NODE_UID_INFO: MY_MAX_UID=" << my_max_node_uid
          << " GLOBAL=" << global_max_node_uid;
 
  //TODO: choose a good value to initialize the table
  BoundaryInfosMap boundary_infos_to_send(nb_rank, true);
  NodeUidToSubDomain uid_to_subdomain_converter(global_max_node_uid, nb_rank);
  info() << "NB_CORE modulo=" << uid_to_subdomain_converter.modulo();
  HashTableMapT<Int64, SharedArray<Int64>> nodes_info(100000, true);
  IItemFamily* node_family = m_mesh->nodeFamily();
  UniqueArray<bool> is_boundary_nodes(node_family->maxLocalId(), false);
 
  // Marks all boundary nodes because these are the ones that need to be sent
  faces_map.eachItem([&](Face face) {
    Integer face_nb_cell = face.nbCell();
    if (face_nb_cell == 1) {
      for (Node node : face.nodes())
        is_boundary_nodes[node.localId()] = true;
    }
  });
 
  // Determines the list of boundary faces
  faces_map.eachItem([&](Face face) {
    Node first_node = face.node(0);
    Int64 first_node_uid = first_node.uniqueId();
    SharedArray<Int64> v;
    Int32 dest_rank = -1;
    if (!is_boundary_nodes[first_node.localId()]) {
      v = nodes_info.lookupAdd(first_node_uid)->value();
    }
    else {
      dest_rank = uid_to_subdomain_converter.uidToRank(first_node_uid);
      v = boundary_infos_to_send.lookupAdd(dest_rank)->value();
    }
    v.add(first_node_uid); // 0
    v.add(my_rank); // 1
    v.add(face.uniqueId()); // 2
    v.add(face.type()); // 3
    Cell back_cell = face.backCell();
    Cell front_cell = face.frontCell();
    if (back_cell.null()) // 4 : only used for debug
      v.add(NULL_ITEM_UNIQUE_ID);
    else
      v.add(back_cell.uniqueId());
    if (front_cell.null()) // 5 : only used for debug
      v.add(NULL_ITEM_UNIQUE_ID);
    else
      v.add(front_cell.uniqueId());
    for (Integer z = 0, zs = face.nbNode(); z < zs; ++z)
      v.add(face.node(z).uniqueId());
  });
 
  // Positions the list of sends
  Ref<IParallelExchanger> exchanger{ ParallelMngUtils::createExchangerRef(pm) };
  _exchangeData(exchanger.get(), boundary_infos_to_send);
 
  {
    Integer nb_receiver = exchanger->nbReceiver();
    debug() << "NB RECEIVER=" << nb_receiver;
    Int64UniqueArray received_infos;
    for (Integer i = 0; i < nb_receiver; ++i) {
      ISerializeMessage* sm = exchanger->messageToReceive(i);
      //Int32 orig_rank = sm->destSubDomain();
      ISerializer* s = sm->serializer();
      s->setMode(ISerializer::ModeGet);
      Int64 nb_info = s->getInt64();
      //info() << "RECEIVE NB_INFO=" << nb_info << " from=" << orig_rank;
      received_infos.resize(nb_info);
      s->getSpan(received_infos);
      //if ((nb_info % 3)!=0)
      //fatal() << "info size can not be divided by 3";
      Integer z = 0;
      while (z < nb_info) {
        Int64 node_uid = received_infos[z + 0];
        Int32 face_type = (Int32)received_infos[z + 3];
        ItemTypeInfo* itt = itm->typeFromId(face_type);
        Integer face_nb_node = itt->nbLocalNode();
        Int64Array& a = nodes_info.lookupAdd(node_uid)->value();
        a.addRange(Int64ConstArrayView(6 + face_nb_node, &received_infos[z]));
        z += 6;
        z += face_nb_node;
      }
    }
    Integer my_max_face_node = 0;
    for (HashTableMapT<Int64, SharedArray<Int64>>::Enumerator inode(nodes_info); ++inode;) {
      Int64ConstArrayView a = *inode;
      Integer nb_info = a.size();
      Integer z = 0;
      Integer node_nb_face = 0;
      while (z < nb_info) {
        ++node_nb_face;
        Int32 face_type = (Int32)a[z + 3];
        ItemTypeInfo* itt = itm->typeFromId(face_type);
        Integer face_nb_node = itt->nbLocalNode();
        z += 6;
        z += face_nb_node;
      }
      my_max_face_node = math::max(node_nb_face, my_max_face_node);
    }
    Integer global_max_face_node = pm->reduce(Parallel::ReduceMax, my_max_face_node);
    debug() << "GLOBAL MAX FACE NODE=" << global_max_face_node;
    // OK, maintenant donne comme uid de la face (node_uid * global_max_face_node + index)
    IntegerUniqueArray indexes;
    boundary_infos_to_send = BoundaryInfosMap(nb_rank, true);
 
    for (HashTableMapT<Int64, SharedArray<Int64>>::Enumerator inode(nodes_info); ++inode;) {
      Int64ConstArrayView a = *inode;
      Integer nb_info = a.size();
      Integer z = 0;
      Integer node_nb_face = 0;
      indexes.clear();
      while (z < nb_info) {
        Int64 node_uid = a[z + 0];
        Int32 sender_rank = (Int32)a[z + 1];
        Int64 face_uid = a[z + 2];
        Int32 face_type = (Int32)a[z + 3];
        ItemTypeInfo* itt = itm->typeFromId(face_type);
        Integer face_nb_node = itt->nbLocalNode();
 
        // Checks if the face is already in the list:
        Integer face_index = node_nb_face;
        Int32 face_new_owner = sender_rank;
        for (Integer y = 0; y < node_nb_face; ++y) {
          if (memcmp(&a[indexes[y] + 6], &a[z + 6], sizeof(Int64) * face_nb_node) == 0) {
            face_index = y;
            face_new_owner = (Int32)a[indexes[y] + 1];
          }
        }
        Int64 face_new_uid = (node_uid * global_max_face_node) + face_index;
        Int64Array& v = boundary_infos_to_send.lookupAdd(sender_rank)->value();
        // Indicates to the owner of this face its new uid
        v.add(face_uid);
        v.add(face_new_uid);
        v.add(face_new_owner);
        indexes.add(z);
        z += 6;
        z += face_nb_node;
        ++node_nb_face;
      }
      my_max_face_node = math::max(node_nb_face, my_max_face_node);
    }
  }
  exchanger = ParallelMngUtils::createExchangerRef(pm);
 
  _exchangeData(exchanger.get(), boundary_infos_to_send);
  {
    Integer nb_receiver = exchanger->nbReceiver();
    debug() << "NB RECEIVER=" << nb_receiver;
    Int64UniqueArray received_infos;
    for (Integer i = 0; i < nb_receiver; ++i) {
      ISerializeMessage* sm = exchanger->messageToReceive(i);
      ISerializer* s = sm->serializer();
      s->setMode(ISerializer::ModeGet);
      Int64 nb_info = s->getInt64();
      received_infos.resize(nb_info);
      s->getSpan(received_infos);
      if ((nb_info % 3) != 0)
        ARCANE_FATAL("info size can not be divided by 3 v={0}", nb_info);
      ;
      Int64 nb_item = nb_info / 3;
      for (Int64 z = 0; z < nb_item; ++z) {
        Int64 old_uid = received_infos[(z * 3)];
        Int64 new_uid = received_infos[(z * 3) + 1];
        Int32 new_owner = (Int32)received_infos[(z * 3) + 2];
        impl::MutableItemBase face(faces_map.tryFind(old_uid));
        if (face.null())
          ARCANE_FATAL("Can not find own face uid={0}", old_uid);
        face.setUniqueId(new_uid);
        face.setOwner(new_owner, my_rank);
      }
    }
  }
 
  traceMng()->flush();
  pm->barrier();
  debug() << "END OF TEST NEW FACE COMPUTE";
  return;
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
void FaceUniqueIdBuilder::
_computeFacesUniqueIdsSequential()
{
  bool is_verbose = m_mesh_builder->isVerbose();
 
  ItemInternalMap& cells_map = m_mesh->cellsMap();
 
  // In sequential mode, the uniqueIds() of the cells cannot exceed the
  // size of Integers even in 32 bits.
  Int32 max_uid = 0;
  cells_map.eachItem([&](Item cell) {
    Int32 cell_uid = cell.uniqueId().asInt32();
    if (cell_uid > max_uid)
      max_uid = cell_uid;
  });
  info() << "Max uid=" << max_uid;
  Integer nb_computed = max_uid + 1;
  Int32UniqueArray cell_first_face_uid(nb_computed, 0);
  Int32UniqueArray cell_nb_num_back_face(nb_computed, 0);
  Int32UniqueArray cell_true_boundary_face(nb_computed, 0);
 
  cells_map.eachItem([&](Cell cell) {
    Int32 cell_uid = cell.uniqueId().asInt32();
    Integer nb_num_back_face = 0;
    Integer nb_true_boundary_face = 0;
    for (Face face : cell.faces()) {
      if (face.backCell() == cell)
        ++nb_num_back_face;
      else if (face.nbCell() == 1) {
        ++nb_true_boundary_face;
      }
    }
    cell_nb_num_back_face[cell_uid] = nb_num_back_face;
    cell_true_boundary_face[cell_uid] = nb_true_boundary_face;
  });
 
  Integer current_face_uid = 0;
  for (Integer i = 0; i < nb_computed; ++i) {
    cell_first_face_uid[i] = current_face_uid;
    current_face_uid += cell_nb_num_back_face[i] + cell_true_boundary_face[i];
  }
 
  if (is_verbose) {
    cells_map.eachItem([&](Item cell) {
      Int32 i = cell.uniqueId().asInt32();
      info() << "Recv: Cell FaceInfo celluid=" << i
             << " firstfaceuid=" << cell_first_face_uid[i]
             << " nbback=" << cell_nb_num_back_face[i]
             << " nbbound=" << cell_true_boundary_face[i];
    });
  }
 
  cells_map.eachItem([&](Cell cell) {
    Int32 cell_uid = cell.uniqueId().asInt32();
    Integer nb_num_back_face = 0;
    Integer nb_true_boundary_face = 0;
    for (Face face : cell.faces()) {
      Int64 face_new_uid = NULL_ITEM_UNIQUE_ID;
      if (face.backCell() == cell) {
        face_new_uid = cell_first_face_uid[cell_uid] + nb_num_back_face;
        ++nb_num_back_face;
      }
      else if (face.nbCell() == 1) {
        face_new_uid = cell_first_face_uid[cell_uid] + cell_nb_num_back_face[cell_uid] + nb_true_boundary_face;
        ++nb_true_boundary_face;
      }
      if (face_new_uid != NULL_ITEM_UNIQUE_ID) {
        face.mutableItemBase().setUniqueId(face_new_uid);
      }
    }
  });
 
  if (is_verbose) {
    OStringStream ostr;
    cells_map.eachItem([&](Cell cell) {
      Integer face_index = 0;
      for (Face face : cell.faces()) {
        Int64 opposite_cell_uid = NULL_ITEM_UNIQUE_ID;
        bool true_boundary = false;
        bool internal_other = false;
        if (face.backCell() == cell) {
        }
        else if (face.nbCell() == 1) {
          true_boundary = true;
        }
        else {
          internal_other = true;
          opposite_cell_uid = face.backCell().uniqueId().asInt64();
        }
        ostr() << "NEW LOCAL ID FOR CELLFACE cell_uid=" << cell.uniqueId() << ' '
               << face_index << " uid=" << face.uniqueId() << " (";
        for (Node node : face.nodes())
          ostr() << ' ' << node.uniqueId();
        ostr() << ")";
        if (internal_other)
          ostr() << " internal-other";
        if (true_boundary)
          ostr() << " true-boundary";
        if (opposite_cell_uid != NULL_ITEM_ID)
          ostr() << " opposite " << opposite_cell_uid;
        ostr() << '\n';
        ++face_index;
      }
    });
    info() << ostr.str();
  }
}
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
} // End namespace Arcane::mesh
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/