ingles - entrevista con tag questions

C entrevista de trabajo-fundición y comparación

Question

Me enfrenté a una pregunta complicada (IMO). Necesitaba comparar dos direcciones MAC , de la manera más eficiente.

El único pensamiento que cruzó por mi mente en ese momento fue la solución trivial: un bucle for , y la comparación de ubicaciones, y así lo hice, pero el entrevistador tenía como objetivo el casting.

La definición de MAC:

typedef struct macA {
char data[6];
} MAC;

Y la función es (la que se me pidió que implementara):

int isEqual(MAC* addr1, MAC* addr2)
{
int i;
for(i = 0; i<6; i++)
{
if(addr1->data[i] != addr2->data[i])
return 0;
}
return 1;
}

Pero como se mencionó, él estaba apuntando al casting.

Es decir, para emitir de algún modo la dirección MAC dada a una int, comparar ambas direcciones y regresar.

Pero cuando se lanza, int int_addr1 = (int)addr1; , solo cuatro bytes serán convertidos, ¿verdad? ¿Debería revisar los restantes? Significado ubicaciones 4 y 5?

Tanto char como int son tipos enteros, por lo que la conversión es legal, pero ¿qué sucede en la situación descrita?

Answer 1

Esto funcionaría en la mayoría de los sistemas y sería más rápido que tu solución.

int isEqual(MAC* addr1, MAC* addr2)
{
return ((int32*)addr1)[0] == ((int32*)addr2)[0] && ((int16*)addr1)[2] == ((int16*)addr2)[2];
}

se alinearía muy bien también, podría ser útil en el centro del ciclo en un sistema donde se puede verificar que los detalles sean viables.

Answer 2

La función memcmp eventualmente hará el loop en sí mismo. Entonces, al usarlo, básicamente harías las cosas menos eficientes (debido a la llamada de función adicional).

Aquí hay una solución opcional:

typedef struct
{
int x;
short y;
}
MacAddr;
int isEqual(MAC* addr1, MAC* addr2)
{
return *(MacAddr*)addr1 == *(MacAddr*)addr2;
}

El compilador probablemente convertirá este código en dos comparaciones, ya que la estructura MacAddr contiene dos campos.

Cavidad: a menos que su CPU admita operaciones de almacenamiento / carga desalineadas, addr1 y addr2 deben estar alineados a 4 bytes (es decir, deben estar ubicados en direcciones divisibles por 4). De lo contrario, es muy probable que se produzca una infracción de acceso a la memoria cuando se ejecuta la función.

Puede dividir la estructura en 3 campos de 2 bytes cada uno, o 6 campos de 1 byte cada uno (reduciendo la restricción de alineación a 2 o 1 respectivamente). Pero sin olvidar que una sola comparación en su código fuente no es necesariamente una sola comparación en la imagen ejecutable (es decir, durante el tiempo de ejecución).

Por cierto, las operaciones de carga / almacenamiento desalineadas por sí mismas pueden agregar latencia de tiempo de ejecución, si requieren más "nops" en la tubería de la CPU. Esto es realmente una cuestión de arquitectura de la CPU, que dudo que quisieran "profundizar" tan lejos en su entrevista de trabajo. Sin embargo, para afirmar que el código compilado no contiene tales operaciones (si de hecho son "costosas"), podría asegurarse de que las variables siempre estén alineadas con 8 bytes Y añada un #pragma (directiva de compilación) que indique al compilador " no te preocupes por esto ".

Answer 3

No hay nada de malo en una implementación eficiente, por lo que sabe, se ha determinado que este es un código caliente que se llama muchas veces. Y en cualquier caso, está bien que las preguntas de la entrevista tengan restricciones extrañas.

Logical AND es a priori una instrucción de bifurcación debido a la evaluación de cortocircuito incluso si no se compila de esta manera, así que evitemos eso, no lo necesitamos. Tampoco necesitamos convertir nuestro valor de retorno a un verdadero bool ( verdadero o falso , no 0 o cualquier cosa que no sea cero ).

Aquí hay una solución rápida en 32 bits: XOR capturará las diferencias, O registrará la diferencia en ambas partes, y NO anulará la condición en EQUALS, no UNEQUAL. El LHS y el RHS son cálculos independientes, por lo que un procesador superescalar puede hacer esto en paralelo.

int isEqual(MAC* addr1, MAC* addr2)
{
return ~((*(int*)addr2 ^ *(int*)addr1) | (int)(((short*)addr2)[2] ^ ((short*)addr1)[2]));
}

EDITAR
El propósito del código anterior era mostrar que esto podría hacerse de manera eficiente sin ramificación. Los comentarios han señalado que C ++ clasifica esto como un comportamiento indefinido. Si bien es cierto, VS maneja esto bien. Sin cambiar la definición de la estructura del entrevistador y la firma de la función, para evitar un comportamiento indefinido se debe hacer una copia adicional. Entonces, el modo de comportamiento no indefinido sin ramificación pero con una copia extra sería el siguiente:

int isEqual(MAC* addr1, MAC* addr2)
{
struct IntShort
{
int i;
short s;
};
union MACU
{
MAC addr;
IntShort is;
};
MACU u1;
MACU u2;
u1.addr = *addr1; // extra copy
u2.addr = *addr2; // extra copy
return ~((u1.is.i ^ u2.is.i) | (int)(u1.is.s ^ u2.is.s)); // still no branching
}

Answer 4

Para escribir un juego de palabras correctamente, debe usar una unión. De lo contrario, romperá las reglas de alias estricto que siguen ciertos compiladores, y el resultado será indefinido.

int EqualMac( MAC* a , MAC* b )
{
union
{
MAC m ;
uint16_t w[3] ;
} ua , ub ;
ua.m = *a ;
ub.m = *b ;
if( ua.w[0] != ub.w[0] )
return 0 ;
if( ua.w[1] != ub.w[1] )
return 0 ;
if( ua.w[2] != ub.w[2] )
return 0 ;
return 1 ;
}

De acuerdo con C99, es seguro leer de un miembro de la unión que no sea el último usado para almacenar un valor en él.

Si el miembro utilizado para leer el contenido de un objeto de unión no es el mismo que el miembro utilizado por última vez para almacenar un valor en el objeto, la parte apropiada de la representación de objeto del valor se reinterpreta como una representación de objeto en el nuevo tipo como descrito en 6.2.6 (un proceso a veces llamado "tipo de juego de palabras"). Esto podría ser una representación de trampa.

Answer 5

Puede ser que tuviera en mente una definición de MAC que usaba char sin signo y pensaba:

int isEqual(MAC* addr1, MAC* addr2) { return strncmp((*addr1).data,(*addr2).data,6)==0; }

lo que implica un lanzamiento de (char sin signo *) a (char *). De todos modos mala pregunta.

Answer 6

Si él está realmente insatisfecho con este enfoque (que es esencialmente un pedo cerebral, ya que no está comparando megabytes o gigabytes de datos, entonces uno realmente no debe preocuparse por la "eficiencia" y la "velocidad" en este caso), solo dile que confías en la calidad y velocidad de la biblioteca estándar:

int isEqual(MAC* addr1, MAC* addr2)
{
return memcmp(&addr1->data, &addr2->data, sizeof(addr1->data)) == 0;
}

Answer 7

Si su entrevistador exige que usted produzca un comportamiento indefinido, probablemente buscaría un trabajo en otro lugar.

El enfoque inicial correcto sería almacenar la dirección MAC en algo así como uint64_t , al menos en la memoria. Entonces las comparaciones serían triviales e implementables de manera eficiente.

Answer 8

Solución de fundición no portátil.

En una plataforma que uso (basada en PIC24), hay un tipo int48 , por lo que es una asunción segura char es de 8 bits y los requisitos de alineación habituales:

int isEqual(MAC* addr1, MAC* addr2) {
return *((int48_t*) &addr1->data) == *((int48_t*) &addr2->data);
}

Por supuesto, esto no se puede usar en muchas plataformas, pero también lo son algunas soluciones que no son portátiles, dependiendo del tamaño int asumido, el no padding , etc.

La solución portátil más alta (y razonablemente rápida dada una buena compilación) es la memcmp() ofrecida por @ H2CO3.

Ir a un nivel de diseño más alto y usar un tipo entero lo suficientemente ancho como uint64_t lugar de struct macA , como lo sugiere Kerrek SB, es muy atractivo.

Answer 9

Tiempo de vaquero:

typedef struct macA {
char data[6];
} MAC;
typedef struct sometimes_works {
long some;
short more;
} cast_it
typedef union cowboy
{
MAC real;
cast_it hack;
} cowboy_cast;
int isEqual(MAC* addr1, MAC* addr2)
{
assert(sizeof(MAC) == sizeof(cowboy_cast)); // Can''t be bigger
assert(sizeof(MAC) == sizeof(cast_it)); // Can''t be smaller
if ( ( ((cowboy_cast *)addr1)->hack.some == ((cowboy_cast *)addr2)->hack.some )
&& ( ((cowboy_cast *)addr1)->hack.more == ((cowboy_cast *)addr2)->hack.more ) )
return (0 == 0);
return (0 == 42);
}

Answer 10

Usted tiene una estructura MAC (que contiene una matriz de 6 bytes),

typedef struct {
char data[6];
} MAC;

Lo cual concuerda con este artículo sobre typedef para array de bytes de longitud fija .

El enfoque ingenuo sería asumir que la dirección MAC está alineada con las palabras (que es probablemente lo que el entrevistador quería), aunque no está garantizada.

typedef unsigned long u32;
typedef signed long s32;
typedef unsigned short u16;
typedef signed short s16;
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1); //check for NULL args
u32 m1 = *(u32*)mac1->data;
U32 m2 = *(u32*)mac2->data;
if( m1 != m2 ) return (s32)m1 - (s32)m2;
u16 m3 = *(u16*)(mac1->data+4);
u16 m2 = *(u16*)(mac2->data+4);
return (s16)m3 - (s16)m4;
}

Un poco más seguro sería interpretar el char [6] como un short [3] (es más probable que MAC esté alineado en los límites de byte par que impar),

typedef unsigned short u16;
typedef signed short s16;
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1); //check for NULL args
u16* p1 = (u16*)mac1->data;
u16* p2 = (u16*)mac2->data;
for( n=0; n<3; ++n ) {
if( *p1 != *p2 ) return (s16)*p1 - (s16)*p2;
}
return(0);
}

No asuma nada, y copie a almacenamiento alineado a palabras, pero la única razón para encasillar aquí es satisfacer al entrevistador,

typedef unsigned short u16;
typedef signed short s16;
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1); //check for NULL args
u16 m1[3]; u16 p2[3];
memcpy(m1,mac1->data,6);
memcpy(m2,mac2->data,6);
for( n=0; n<3; ++n ) {
if( m1[n] != m2[n] ) return (s16)m1[n] - (s16)m2[n];
}
return(0);
}

Ahórrese mucho trabajo,

int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1);
return memcmp(mac1->data,mac2->data,6);
}